如何求N以内的约数总数？

发布于 2024-12-02 23:58:38 字数 294 浏览 2 评论 0原文

给定数字 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

原文

Given a number N, have to find number the divisors for all i where i>=1 and i<=N. Can't figure it out.Do I have to this using prime factorization? Limit is N<=10^9
Sample Output:

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

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

靖瑶 2024-12-09 23:58:38

要加快计算速度，请使用以下伪代码：

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

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

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

回复收藏 0 原文

匿名。 2024-12-09 23:58:38

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

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

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

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

回复收藏 0 原文

我要还你自由 2024-12-09 23:58:38

不确定您使用的是什么语言，但基本思想如下：

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 mod 2 = 0 （...
10 mod 3 = 1 （因为 3 等于 10 3 次，余数为 1）
10 mod 4 = 2（因为 4 等于 10 2 次，余数为 2）

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

。 For 循环的编写方式可能与您使用的语言略有不同。上面的代码是 VB。但是如果您查看书籍索引，您可能会发现这两个常见功能的语言版本。

..)并且 strong>编辑

好的——在这种情况下，只需添加另一个 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

Not sure what language you're using, but here's the basic idea:

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

Notes:

Mod gives you the remainder of division. So for example:
10 mod 1 = 0 (because 1 goes into 10 10-times exactly)
10 mod 2 = 0 (...
10 mod 3 = 1 (because 3 goes into 10 3-times, with a remainder of 1)
10 mod 4 = 2 (because 4 goes into 10 2-times, with a remainter of 2)

You only want to count the results where N mod i = 0, because those are the only instances where i goes into N with no remainder; which I think is what your teacher probably means when they say 'divisor' -- no remainder.

The variable declarations (dim...) and the For loop might be written slightly differently in whatever language you're using. The code above is VB. But if you look in your book index, you'll probably find your language's version of these two common features.

EDIT

OK -- in that case, just add another FOR loop, as follows:

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

回复收藏 0 原文

~没有更多了~