如何找到N的除数总数？

Question

给定数字N,必须找到所有i的除数,其中i> = 1且i <= N. 无法理解.我是否需要使用素数分解？限制为N <= 10 ^ 9样本输出:

1 --> 1
2 --> 3
3 --> 5
4 --> 8
5 --> 10
6 --> 14
7 --> 16
8 --> 20
9 --> 23
10 --> 27
11 --> 29
12 --> 35
13 --> 37
14 --> 41
15 --> 45

Answer 1

要计算得更快,请使用以下伪代码:

sum = 0; u = floor(sqrt(N)); foreach k <= u, sum += Floor(N / K); sum = 2*sum-u*u

上述公式由Peter Gustav Lejeune Dirichlet在19世纪给出.

我用上面的算法编写了一个C程序,在我的计算机上花了0.118秒来计算从1到10 ^ 14的除数数之和.答案是3239062263181054.