1

数Nが与えられた場合、i>=1およびi<=Nであるすべてのiの約数の数を見つける必要があります。理解できません。素因数分解を使用してこれを行う必要がありますか？制限は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世紀のペーターグスタフレジューヌディリクレによって与えられました。

上記のアルゴリズムを使用して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 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になり、余りがない唯一のインスタンスであるためです。これは、先生が「除数」と言ったときにおそらく意味することだと思います。余りはありません。

変数宣言（dim ...）とForループは、使用している言語によって少し異なる方法で記述される場合があります。上記のコードはVBです。しかし、本の索引を見ると、おそらくこれら2つの一般的な機能の言語バージョンが見つかります。

編集

OK-その場合は、次のように別の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 に答える