確かにこの記事を複数回読んだ人は皆、少なくともエラトステネスのふるい-素数を見つける方法を聞いたことがあります。 素数を取得するという問題自体が数学の重要な位置を占めており、RSAなどの一部の暗号化アルゴリズムはそれに基づいています。 この問題にはかなりの数のアプローチがありますが、この記事ではそれらの最も単純なものであるエラトステネスのふるいのいくつかの修正に焦点を当てます。
ふるいの原理は単純です：ユニティからいくつかのN <= 10 ^ 6までの区間で素数を見つける必要があるとします。 N個の要素で配列を開始し、trueで埋めます。 その後、Nのルートまで連続して進み、trueを満たし、このステップですべての数値をNに取り消します。アルゴリズムはコンパクトでシンプルに見えます。javaで引用しています。
Arrays.fill(isPrime, true ); isPrime[ 1 ] = false ; for ( int i= 2 ; i*i < N; i++) if (isPrime[i]) for ( int j=i*i; j < N; j+=i) isPrime[j] = false ;
Arrays.fill(isPrime, true ); isPrime[ 1 ] = false ; for ( int i= 2 ; i*i < N; i++) if (isPrime[i]) for ( int j=i*i; j < N; j+=i) isPrime[j] = false ;
Arrays.fill(isPrime, true ); isPrime[ 1 ] = false ; for ( int i= 2 ; i*i < N; i++) if (isPrime[i]) for ( int j=i*i; j < N; j+=i) isPrime[j] = false ;
Arrays.fill(isPrime, true ); isPrime[ 1 ] = false ; for ( int i= 2 ; i*i < N; i++) if (isPrime[i]) for ( int j=i*i; j < N; j+=i) isPrime[j] = false ;
Arrays.fill(isPrime, true ); isPrime[ 1 ] = false ; for ( int i= 2 ; i*i < N; i++) if (isPrime[i]) for ( int j=i*i; j < N; j+=i) isPrime[j] = false ;
Arrays.fill(isPrime, true ); isPrime[ 1 ] = false ; for ( int i= 2 ; i*i < N; i++) if (isPrime[i]) for ( int j=i*i; j < N; j+=i) isPrime[j] = false ;
このアルゴリズムはO（N * log（log（N）））で機能するため、小さな数値に非常に適しています。 1からNまでではなく、nからmまでの素数を見つける必要がある場合を考えます。 1 <= m <= n <= 10 ^ 9;という制限を設けましょう。 nm <= 10 ^ 6 。 ここでは、ダブルシーブと呼ばれるアルゴリズムを適用する必要があります。 これは、nのルートまでの素数を見つけ、それらを別の配列に格納し、同じ方法でこれらの素数を特定のステップで「削除」することですが、間隔[m、n]から必要です。 簡単に言うと、このアルゴリズムは次のようになります。
- int primes = new int [P]; //単純にnの根まで埋めます
- ブールふるい= 新しい ブール [n-m + 1 ]; //二次ふるい
- Arrays.fill（sieve、 true ）;
- for （ int i = 0 ; i <P; i ++）{
- int h = m％素数[i];
- int j = h == 0 ？ 0 ：素数[i]-h;
- for （; j <= nm; j + = primes [i]）
- ふるい[j] = false ;
したがって、ゼロから十分に離れた範囲に対処できます。 ここで最も興味深い点に行きます：0からN = 10 ^ 8までの素数を出力する必要がある場合はどうでしょうか？ 漸近性を思い出すと、一見すると通常のふるいでも本当のように見えますが、メモリコスト：10 ^ 8 * 4 = 400MBを見ると、特に制限時間が厳しい場合、タスクはそれほど簡単ではないことがわかります。 この問題を解決するには、次の2つのアプローチを区別できます。
- ふるい包装
- キャッシュ数
それらについてもう少し詳しく考えてみましょう。 パッケージは次のとおりです。最新のプログラミング言語では、ブール型は平均で1〜4バイトかかりますが、1ビットだけでエンコードできます。 したがって、整数の配列を作成し、それぞれをビットマスクとして使用して、メモリを8〜30倍節約できます。 利点はすぐにわかりますが、2番目のアイデアについてもう少し詳しく見てみましょう。
多くの人は、コンピューターにはプロセッサーとRAMの間にキャッシュメモリがあり、RAMを使用するよりもはるかに高速に動作することを知っていますが、サイズは限られています。 たとえば、大きなアレイで作業する場合、プロセッサはその一部をキャッシュにロードし、それを処理してから、操作可能なアレイに戻し、別のアレイをロードします。 そして、ふるいアルゴリズムを思い出しましょう。配列全体から各素数を消し、最初から最後までそれを通過します。 そのため、プロセッサはアレイのさまざまなセグメントをキャッシュに何度もロードし、この速度は大幅に低下します。 このアプローチでは、あるメモリから別のメモリにアレイをコピーするコストを最小限に抑えることをお勧めします。 間隔全体をキャッシュのサイズにほぼ等しい3 * 10 ^ 4個までの要素に分割し、それらを順番に処理する場合、これを行うのは難しくありません。 次に、最小のダウンロード数でアレイ全体を処理します。 次のようになります。
- int CACHE = 30000 ; //キャッシュサイズ
- int M =（ int ） Math .sqrt（N）+ 1 ;
- int primes = new int [P]; // Nのルートに対する素数の配列
- ブールセグメント= 新しい ブール [CACHE]; //二次ふるい
- for （ int I = M- 1 ; I <N; I + = CACHE）{
- Arrays.fill（segment、 true ）;
- for （ int i = 0 ; i <P; i ++）{
- int h = I％primes [i];
- int j = h> 0 ？ 素数[i]-h： 0 ;
- for （; j <CACHE; j + = primes [i]）
- セグメント[j] = false ;
- }
- for （ int i = 0 ; i <CACHE; i ++）{
- if （セグメント[i] &&（i + I <N））{
- out .println（i + I）; //素数を画面に出力します
- }
- }
- }
この方法を使用すると、実際には複雑化せずにふるいを大幅に加速します。たとえば、 TDPRIMESの多くのタスクでは、これが大幅に役立ちます。このタスクでは、通常のふるいが10秒に収まらず、セグメント化されたものが通過することがよくわかります2.8。