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

Question

我必须找到所有数字的因子总数2 to N.

这是我的方法.

运行Sieve of Eratosthenes并获取所有素数2 to N.

对于每个数字2 to N,进行素数因子分解并获得所有素因子的指数.添加1到每个素因子指数并乘以所有指数,即,

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

然后,

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

是否有任何替代/有效的方法可以有效地计算第一N自然数的因子总数.

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

例1,从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