0

最大100,000,000をふるいにかけて素数を生成したいのですが、この範囲のブール配列を宣言するとプログラムがクラッシュします。これは私のコードです：

long long i,j,n;
bool prime[100000000+1];
prime[1]=prime[0]=false;
for(i=2;i<=100000000;i++){
    prime[i]=true;
}
for(i=2;i<=100000000;i++){
    if(prime[i]==false){
        continue;
    }
    for(j=i*2;j<=100000000;j+=i){
        prime[j]=false;
    }
}

どうすればこの問題を解決できますか？

4

3 に答える 3

3

配列プライムのサイズは100MBであり、スタック上で非常に大きな配列を宣言することは許可されていません。配列をグローバルスコープに配置してヒープに割り当てるか、new（in C++）またはmalloc（in）を使用して配列を割り当ててみてくださいC。その後、メモリを解放することを忘れないでください！

于 2013-03-25T15:54:57.073 に答える
2

変数は、静的メモリ、自動メモリ、動的メモリの3つの異なるメモリ領域に格納できます。自動メモリ（非静的ローカル変数）のサイズには制限があり、それを超えたため、プログラムがクラッシュしました。別の方法は、アレイを静的にマークすることです。これにより、アレイが静的ストレージに配置されるか、ダイナミックメモリが使用されます。

これはC++とタグ付けされているので...使用std::vectorが簡単で動的メモリを使用します。

#include <vector>
//...
//...
long long i,j,n;
std::vector<bool> prime(100000000+1, true);
prime[1]=prime[0]=false;
for(i=2;i<=100000000;i++){
    if(prime[i]==false){
        continue;
    }
    for(j=i*2;j<=100000000;j+=i){
        prime[j]=false;
    }
}

std::vector<bool>「ビット効率の高い」表現を使用します。つまり、ここでのstd :: vectorは、従来の配列の約81分の1のメモリしか使用しません。

std::bitsetは似ていますが、サイズは一定であり、自動メモリのスペースをとらないように静的としてマークする必要があります。

質問はしていませんが、Erastostenes Sieveは、多くの素数を計算するための最速のアルゴリズムではありません。アトキンのふるいはより速く、より少ないメモリを使用しているようです。

1-システムに8ビットバイトがある場合。

于 2013-03-25T16:19:13.100 に答える
1

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

20のセグメントで100から200までふるいにかける例を考えてみましょう。5つのふるい分け素数は3、5、7、11、13です。100から120までの最初のセグメントでは、ビット配列に10個のスロットがあり、スロット0は101に対応し、スロットkは100 + 2 * k *+1に対応します。スロット9は119に対応します。セグメント内の3の最小公倍数は105で、スロット2に対応します。スロット2+3=5および5+3 = 8も3の倍数です。スロット2では5の最小公倍数は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には、ふるいへのオフセットが含まれています対応するふるい分け素数の現在のセグメントの最小公倍数のビット配列。各セグメントの後、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

上記のサンプルでは、​​これはと呼ばれ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に対応します。

デルタの値は重要です。速度を上げるために、デルタをキャッシュメモリに収まる限りできるだけ大きくする必要があります。ビット配列に言語のライブラリを使用して、ふるいの場所ごとに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

あなたは私のブログで素数を含むより多くのアルゴリズムを見ることができます。

于 2013-03-25T16:36:39.550 に答える