什么是找到前N个自然数的因子数量的最佳算法？

Question

我需要找到从 2 到 N 所有数字的因子总数。

这是我的方法。

运行 Eratosthenes 筛法 并获取从 2 到 N 的所有质数。

对于从 2 到 N 的每个数字，进行质因数分解并获取所有质因数的指数。将每个质因数的指数加上 1 并乘以所有指数，即：

N = 2^x1 * 3^x2 * 5*x^3 ...

然后，

Number of factors = (x1 + 1) * (x2 + 1) * (x3 + 1) ...

有没有其他高效的方法可以计算前 N 个自然数的因子总数。

- Sai Nikhil

---

无法接受非公共链接。 - user1196549

已删除链接。谢谢。 - Sai Nikhil

Answer 1

在2和N之间的所有整数的因子数量可以通过以下公式以O（N）的时间复杂度计算出来：

total = N/1 + N/2 + ... + N/N - 1. (integer division)

2和N之间的任何整数x都是2到N之间以下整数的因子：x, 2x, 3x, 4x, ..., (N/x)x

例如，从2到6的数字的因子总数为13: 6/1 + 6/2 + 6/3 + 6/4 + 6/5 + 6/6 - 1 = 6+3+2+1+1+1-1 = 13

These are the factors:
2: 1, 2
3: 1, 3
4: 1, 2, 4
5: 1, 5
6: 1, 2, 3, 6

2, 3, and 5 all have 2 factors, 4 has 3, and 6 has 4, for a total of 13.

如果你只想要质因数:

total = N/p1 + N/p2 + ... + N/pk where pk is the largest prime <= N.

例如，N=6: 6/2 + 6/3 + 6/5 = 6

2: 2
3: 3
4: 2
5: 5
6: 2, 3

- Dave

---

OP希望得到所有的因数，正如问题中“因数个数”的公式所示。你的算法非常出色，点赞！但是你在最后一段的解释可以更好些。通过仅对N/(N-1)进行求和并省略N/N和-1，你可以避免最后的减法1。 - Rory Daulton

这个问题要求计算因数的数量，而 OP 的公式明确表明他想要找到因数的数量。https://brilliant.org/wiki/factors/。如果你想找到所有的因数，如果你从 1 到 N 运行所有的数字，时间复杂度将会比 OP 当前拥有的 O(N^2) 更差。 - Pham Trung

这是O(N^2)的时间复杂度。对于大规模的‘N’来说不太适用。我们有没有办法可以进行优化呢？ - Sai Nikhil

@PhamTrung：这个算法不是O(N^2)，而是O(N)。有N个整数除法，N-1个加法和1个减法（在Dave的原始形式中）。 Dave算法的重点在于它永远不会找到任何数字的因子 - 它们最终以一种不同且更短的方式被计算。 Dave的算法确实可以正常工作 - 我测试了所有值为N的情况，最高达10,000，将其结果与更直接、更慢的方法进行比较。我删除了自己的答案，因为他的答案要好得多。 - Rory Daulton

@SaiNikhil 这是O(N)的时间复杂度，正如Rory在上面解释的那样。 - Dave