1

私の仕事は、12 桁までのすべての素数を含む配列を作成することです。

最初に、2 から までのすべての整数を含む配列を生成する関数を作成して、エラトステネスのふるいをエミュレートしようとしました。enumeratenum

var enumerate = function(num) {
    array = [];
    for (var i = 2; i <= num; i++) {
        array.push(i);
    }
    return array;
};

次に、leaveOnlyPrimesループして配列から 1/2 までのすべての配列メンバーの倍数を削除する関数を作成しmaxました (配列は反復ごとに小さくなるため、これはすべての整数にはなりません)。

var leaveOnlyPrimes = function(max,array) {
    for (var i = 0; array[i] <= max/2; i++) {
        (function(mult,array) {
            for (var i = mult*2; i <= array[array.length-1]; i += mult) {
                var index = array.indexOf(i);
                if (index !== -1) {
                    array.splice(index,1);
                }
            }
        })(array[i],array);   
    }
};

これは、約 50000 までの数値で問題なく動作しますが、それ以上になるとブラウザーがフリーズするようです。

より大きな数に対応するために作成できるこのアプローチのバージョンはありますか、それとも間違ったツリーを吠えていますか?

4

2 に答える 2

1

@WillNess が示唆しているように、そのサイズの単一のモノリシックふるいを作成するべきではありません。代わりに、セグメント化されたエラトステネスのふるいを使用して、連続したセグメントでふるい分けを実行します。最初のセグメントでは、セグメント内にある各ふるい素数の最小倍数が計算され、ふるい素数の倍数が通常の方法で合成としてマークされます。すべてのふるい素数が使用されると、セグメント内の残りのマークされていない数が素数になります。次に、次のセグメントでは、各ふるい素数の最小倍数は、前のセグメントでふるい分けを終了した倍数であるため、ふるい分けは終了するまで続行されます。

20 のセグメントで 100 から 200 までふるい分ける例を考えてみましょう。5 つのふるい素数は 3、5、7、11、13 です。100 から 120 までの最初のセグメントでは、bitarray には 10 個のスロットがあり、スロット 0 は 101 に対応し、スロットkは 100 + 2*k* + 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の平方根より大きくなければなりません。セグメント サイズはdeltaの 2 倍です。長さmの配列psには、通常のエラトステネスのふるいで計算された偶数が無視されるため、hiの平方根よりも小さいふるい素数が含まれます。2 は削除されます。配列qsにはふるいへのオフセットが含まれます対応するふるい素数の現在のセグメントの最小倍数の bitarray。各セグメントの後、loはdeltaの2 倍進むため、ふるいbitarrayのインデックス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

上記のサンプルでは、​​これは と呼ばれprimes(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

JavaScriptへの翻訳はお任せします。私のブログで、素数を含むその他のアルゴリズムを参照できます。

于 2013-08-09T23:36:11.183 に答える
1

12 桁までは 100,000,000,000 です。これは多くの素数です (~ N/log N = 3,948,131,653)。

したがって、最大 10^6 のふるいを作成し、それを ~78,500 個のコア素数の配列に圧縮し、それらを使用してセグメントごとにターゲットまでふるいにかけます。セグメントの現在の上限の平方根まで素数を使用します。通常、セグメントのサイズは、システム キャッシュに収まるように選択されます。各セグメントをふるいにかけた後、その素数を収集します。

これは、エラトステネスの分割ふるいとして知られています。

于 2013-08-09T20:12:09.183 に答える