primes - 素数の合計として数値を見つける方法は?

Question

2 つの素数の和として表される 1 から 1000 までのすべての数を見つけたいと考えています。例: 8 = 3+5、24 = 13+11

これは、1 から 1000 までの素数のリストを反復処理することにより、O(n^2) で実行できます。

O(n^2)未満で同じことをする方法はありますか?線形時間でこれを行う方法はありますか?

score 8 · Accepted Answer

現在知られているすべての偶数は、2 つの素数の和として表すことができます (ゴールドバッハの予想を参照) 。

すべての奇数について、2 つの素数の和として表すことができる場合、そのうちの 1 つが 2 で、もう 1 つが奇素数でなければなりません。

したがって、合計数は (1000/2 - 1) + (3 から 997 までの素数カウント) になるはずです。

その中で、

(1000/2 - 1) はシリーズ 4、6、8、10 の合計数です...

(3 から 997 までの素数のカウント) は、シリーズ 5(2+3)、7(2+5)、9(2+7)、13(2+11) ... の合計数です。

score 2 · Accepted Answer

p1000 個のブール値の配列を作成します。が素数の場合に設定p[i]し、そうでない場合に設定します。trueifalse

次に、O(N^2)アルゴリズムは簡単になります。k外側のループで 1 から 1000までの数字を調べてから、内側のループxよりも大きいすべての素数を調べて、次のような素数がk存在するかどうかを確認します。p[k-x]true

for k in 1..1000
    for x in primes greater than k
        if (p[x-k])
            print k can be represented as x plus (x-k)
            break

現在、コンピューター支援による検証はかなり遅い速度で進行しているためO(N)、1000 の数字の合計実行時間に対して一定の時間でチェックを実行できるとは思えません。

5 に答える 5