41

シンプルなふるいを作るのは簡単です：

for (int i=2; i<=N; i++){
    if (sieve[i]==0){
        cout << i << " is prime" << endl;
        for (int j = i; j<=N; j+=i){
            sieve[j]=1;
        }
    }
    cout << i << " has " << sieve[i] << " distinct prime factors\n";
}

しかし、N が非常に大きく、そのような配列をメモリに保持できない場合はどうでしょうか? セグメント化されたふるいのアプローチを調べましたが、sqrt(N) まで素数を見つける必要があるようですが、それがどのように機能するかわかりません。N が非常に大きい (たとえば 10^18) 場合はどうなるでしょうか。

4

6 に答える 6

56

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

nのサイズは重要ではありませんが、大きなnは小さなnよりもふるい分けに時間がかかります。重要なサイズは、セグメントのサイズです。これは、都合のよい大きさにする必要があります (たとえば、マシンのプライマリ メモリ キャッシュのサイズ)。

ここでは、セグメント化されたふるいの簡単な実装を確認できます。セグメント化されたふるいは、別の回答で言及されているオニールの優先キューふるいよりもはるかに高速になることに注意してください。興味があれば、ここに実装があります。

編集：別の目的でこれを書きましたが、役に立つかもしれないのでここに示します：

エラトステネスのふるいは非常に高速ですが、O(n) のスペースが必要です。これは、連続するセグメントでふるい分けを実行することにより、ふるい素数の O(sqrt(n)) と bitarray の O(1) に減らすことができます。最初のセグメントでは、セグメント内にある各ふるい素数の最小倍数が計算され、ふるい素数の倍数が通常の方法で合成としてマークされます。すべてのふるい素数が使用されると、セグメント内の残りのマークされていない数が素数になります。次に、次のセグメントでは、各ふるい素数の最小倍数は、前のセグメントでふるい分けを終了した倍数であるため、ふるい分けは終了するまで続行されます。

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 の倍数です。

関数 primesRange は、引数 lo、hi、および delta を取ります。lo と hi は偶数であり、lo < hi であり、lo は sqrt(hi) より大きくなければなりません。セグメント サイズはデルタの 2 倍です。Ps は sqrt(hi) より小さいふるい素数を含む連結リストで、偶数は無視されるため 2 が削除されます。Qs は、対応するふるい素数の現在のセグメント内の最小倍数のふるい bitarray へのオフフェストを含むリンク リストです。各セグメントの後、lo はデルタの 2 倍進むため、ふるいビット配列のインデックス i に対応する数値は、lo + 2i + 1 になります。

function primesRange(lo, hi, delta)
    function qInit(p)
        return (-1/2 * (lo + p + 1)) % p
    function qReset(p, q)
        return (q - delta) % p
    sieve := makeArray(0..delta-1)
    ps := tail(primes(sqrt(hi)))
    qs := map(qInit, ps)
    while lo < hi
        for i from 0 to delta-1
            sieve[i] := True
        for p,q in ps,qs
            for i from q to delta step p
                sieve[i] := False
        qs := map(qReset, ps, qs)
        for i,t from 0,lo+1 to delta-1,hi step 1,2
            if sieve[i]
                output t
        lo := lo + 2 * delta

primesRange(100, 200, 10) として呼び出された場合、ふるい素数 ps は [3, 5, 7, 11, 13] です。qs は最初は最小の倍数 105、105、105、121、および 117 に対応する [2, 2, 2, 10, 8] であり、2 番目のセグメントでは最小の倍数に対応する [1, 2, 6, 0, 11] にリセットされます。 123、125、133、121、143 の倍数。

このプログラムの動作は次の URL で確認できます。http://ideone.com/iHYr1f . また、上記のリンクに加えて、素数を使ったプログラミングに興味がある場合は、私のブログでこのエッセイをお勧めします。

于 2012-04-20T16:15:54.853 に答える
5

すべての素数を上限までではなく、要求した数だけ素数を生成する優先キューに基づく Sieve のバージョンがあります。それは古典的な論文「エラトステネスのふるい」で議論されており、 「エラトステネスのふるい優先キュー」をグーグルで検索すると、さまざまなプログラミング言語でかなりの数の実装が見つかります。

于 2012-04-20T15:53:22.913 に答える
0

それより小さい素数で割り切れない場合、その数は素数です。素数を順番に繰り返し処理するため、少なくとも 1 つの素数で割り切れるすべての数を割り切れるとすでにマークしています。したがって、セルに到達してもマークされていない場合、そのセルはそれより小さい素数では割り切れないため、素数でなければなりません。

これらの点を覚えておいてください:-

// Generating all prime number up to  R
 
// creating an array of size (R-L-1) set all elements to be true: prime && false: composite
     

#include<bits/stdc++.h>

using namespace std;

#define MAX 100001

vector<int>* sieve(){
    bool isPrime[MAX];

    for(int i=0;i<MAX;i++){
        isPrime[i]=true;
    }
 for(int i=2;i*i<MAX;i++){
     if(isPrime[i]){
         for(int j=i*i;j<MAX;j+=i){
             isPrime[j]=false;
         }
     }
 }

 vector<int>* primes = new vector<int>();
 primes->push_back(2);
 for(int i=3;i<MAX;i+=2){
     if(isPrime[i]){
     primes->push_back(i);
     }
}

 return primes;
}

void printPrimes(long long l, long long r, vector<int>*&primes){
      bool isprimes[r-l+1];
      for(int i=0;i<=r-l;i++){
          isprimes[i]=true;
      }

      for(int i=0;primes->at(i)*(long long)primes->at(i)<=r;i++){

          int currPrimes=primes->at(i);
          //just smaller or equal value to l
          long long base =(l/(currPrimes))*(currPrimes);
      

          if(base<l){
              base=base+currPrimes;
          }
    
    //mark all multiplies within L to R as false

          for(long long j=base;j<=r;j+=currPrimes){
              isprimes[j-l]=false;
          }

   //there may be a case where base is itself a prime number

          if(base==currPrimes){
              isprimes[base-l]= true;
          }
    }

          for(int i=0;i<=r-l;i++){
              if(isprimes[i]==true){
                  cout<<i+l<<endl;
              }
          

      }
}
int main(){
    vector<int>* primes=sieve();
   
   int t;
   cin>>t;
   while(t--){
       long long l,r;
       cin>>l>>r;
       printPrimes(l,r,primes);
   }

    return 0;

}
于 2021-01-17T12:49:23.633 に答える