1

给定一个数 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
4

3 回答 3

12

要更快地计算，请使用以下伪代码：

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

上述公式是 19 世纪的 Peter Gustav Lejeune Dirichlet 给出的。

我使用上述算法编写了一个 C 程序，在我的计算机上计算从 1 到 10^14 的除数之和需要 0.118 秒。答案是 3239062263181054。

于 2013-07-16T05:46:27.063 回答
2

如果要找到给定 N 以内的所有除数之和，则不需要任何因式分解。您可以（例如）以这种方式使用独特的循环来执行此操作。从 2 开始，2 是 2*2、3*2、4*2 等的除数。这给出了背后的想法。

Foreach k < N, Floor(N / k) 是 k 是某事物 < N 的除数的次数。

伪代码：
sum = 0; foreach k <= N sum += Floor(N / K)

请注意，这与询问给定 N 的除数数量不同。

于 2011-12-01T07:03:15.447 回答
0

不确定您使用的是哪种语言，但基本思路如下：

dim myCount as integer = 1
dim N as integer = 10000000000 '10,000,000,000

For i as integer = 2 to N
   If N mod i = 0 Then
      myCount += 1
   End If
Next i

笔记：

  • Mod 为您提供除法的剩余部分。例如：
  • 10 mod 1 = 0（因为 1 正好是 10 的 10 倍）
  • 10 模 2 = 0 (...
  • 10 mod 3 = 1（因为 3 进入 10 3 次，余数为 1）
  • 10 mod 4 = 2（因为 4 进入 10 2 次，余数为 2）

您只想计算 N mod i = 0 的结果，因为这些是 i 无余数进入 N 的唯一实例；我认为这就是你的老师在说“除数”时可能的意思——没有余数。

无论您使用何种语言，变量声明 (dim...) 和 For 循环的编写方式都可能略有不同。上面的代码是VB。但是，如果您查看您的图书索引，您可能会发现这两个共同特征的语言版本。

编辑

好的——在这种情况下，只需添加另一个 FOR 循环，如下所示：

dim myCount as integer = 1
dim N as integer = 10000000000 '10,000,000,000

For i as integer = 1 to N
   For j as integer = 2 to i
      If i mod j = 0 Then
         myCount += 1
      End If
   Next j
Next i
于 2011-09-06T17:27:21.020 回答