4

私は、10 ^ 12 までのすべての素数を生成する必要があることに取り組んでいます。

これまでこれほど多くの素数を必要としたことはなかったので、通常はこの Web ページでアルゴリズムを実装するだけです。

もちろん、ここでの問題は、10^12 が整数の最大値よりも大きく、その結果、そのサイズの配列を作成できないことです。

非常に多くの素数を効率的に生成するために使用する方法に慣れていないため、誰かが状況に光を当てることができるかどうか疑問に思っていました.

4

3 に答える 3

10

セグメント化されたふるいを使用する必要があります。

セグメント化されたふるいの基本的な考え方は、n の平方根よりも小さいふるい素数を選択し、それでもメモリに収まる適度に大きなセグメント サイズを選択してから、最小のものから順に各セグメントをふるいにかけることです。最初のセグメントでは、セグメント内にある各ふるい素数の最小倍数が計算され、ふるい素数の倍数が通常の方法で合成としてマークされます。すべてのふるい素数が使用されると、セグメント内の残りのマークされていない数が素数になります。次に、次のセグメントでは、ふるい分け素数ごとに、現在のセグメントの最初の倍数が既にわかっているため (前のセグメントでその素数のふるい分けを終了したのは倍数でした)、各ふるい素数でふるい分けを行います。あなたが終わるまで。

20 のセグメントで 100 から 200 までふるいにかける例を考えてみましょう。5 つのふるい素数は 3、5、7、11、および 13 です。100 から 120 までの最初のセグメントでは、bitarray には 10 個のスロットがあり、スロット 0 は 101 に対応し、スロット k は 100 + 2k + 1 に対応し、スロット 9 に対応します。 119 に対応します。セグメント内の最小の 3 の倍数は 105 で、スロット 2 に対応します。スロット 2+3=5 および 5+3=8 も 3 の倍数です。5 の最小の倍数はスロット 2 で 105 であり、スロット 2+5=7 も 5 の倍数です。7 の最小の倍数は 105 です。スロット 2 では、スロット 2+7=9 も 7 の倍数です。

関数 primes は、引数 lo、hi、および delta を取ります。lo と hi は、lo < hi で偶数でなければならず、lo は hi の平方根より大きくなければなりません。セグメント サイズはデルタの 2 倍です。長さ m の配列 ps には、通常のエラトステネスのふるいで計算された偶数が無視されるため、hi の平方根よりも小さいふるい素数が含まれます。2 は削除されます。配列 qs には、対応するふるい素数の現在のセグメントの最小倍数のふるい bitarray へのオフセットが含まれます。各セグメントの後、lo はデルタの 2 倍進むため、ふるいビット配列のインデックス i に対応する数値は、lo + 2 i + 1 になります。

function primes(lo, hi, delta)
    sieve := makeArray(0..delta-1)
    ps := tail(primes(sqrt(hi)))
    m := length(ps)
    qs := makeArray(0..m-1)
    for i from 0 to m-1
        qs[i] := (-1/2 * (lo + ps[i] + 1)) % ps[i]
    while lo < hi
        for i from 0 to delta-1
            sieve[i] := True
        for i from 0 to m-1
            for j from qs[i] to delta step ps[i]
                sieve[j] := False
            qs[i] := (qs[i] - delta) % ps[i]
        for i from 0 to delta-1
            t := lo + 2*i + 1
            if sieve[i] and t < hi
                output t
        lo := lo + 2*delta

上記の例では、これは素数 (100, 200, 10) と呼ばれます。上記の例では、qs は最初は [2,2,2,10,8] で、最小の倍数 105、105、105、121、および 117 に対応し、2 番目のセグメントでは [1,2,6, 0,11]、最小の倍数 123、125、133、121、および 143 に対応します。

デルタの値は重要です。速度のために、キャッシュメモリに収まる限りデルタをできるだけ大きくする必要があります。言語のライブラリを bitarray に使用して、ふるいの場所ごとに 1 つのビットのみを取得します。ふるい素数を計算するために単純なエラトステネスのふるいが必要な場合は、これが私のお気に入りです。

function primes(n)
    sieve := makeArray(2..n, True)
    for p from 2 to n step 1
        if sieve(p)
            output p
            for i from p * p to n step p
                sieve[i] := False

これらの関数は両方とも疑似コードです。適切な整数データ型を使用して、Java に変換する必要があります。疑似コードが出力を示している場所では、素数を印刷したり、素数を配列に収集したりできます。

私は自分のブログで素数に関する多くの作業を行ってきました。その中には、最後のページにセグメント化されたふるいを含む「素数によるプログラミング」というエッセイが含まれています。

于 2013-07-06T16:18:11.267 に答える