アトキンのふるい

数学において、アトキンの篩は、指定された整数までのすべての素数を見つけるための現代的なアルゴリズムです。素数の倍数を区別する古代のエラトステネスの篩と比較すると、アトキンの篩はいくつかの予備作業を行ってから素数の平方の倍数を区別することで、より優れた理論的漸近的複雑性を実現します。これは、2003年にAOLアトキンとダニエル・J・バーンスタインによって作成されました。^[1]

アルゴリズムでは：

• すべての余りは-60 を法とした余りです(数値を 60 で割り、余りを返します)。
• xとyを含むすべての数値は正の整数です。
• ふるいリスト内のエントリを反転するということは、マーキング (プライムまたは非プライム) を反対のマーキングに変更することを意味します。
• この結果、対応する方程式の解の数が奇数の場合は潜在的に素数となり（平方数でない場合も素数となります）、解の数が偶数の場合は合成数となります。

アルゴリズム:

1. 2、3、5 が入力された結果リストを作成します。
2. 各正の整数のエントリを含むふるいリストを作成します。このリストのすべてのエントリは、最初は非素数 (合成数) としてマークされている必要があります。
3. ふるいリストの 各エントリ番号nについて、60 を法とした余りがrであるとき :
   1. rが 1、13、17、29、37、41、49、または 53 の場合、各可能な解のエントリを4 x ²  +  y ²  =  nに反転します。このステップのふるい分け範囲に対する比率としての反転操作の数は、⁠に近づきます。4 √π​/15⁠ ^[1] × ⁠8/60⁠ (分数の「8」は、この二次方程式で扱われる 8 つの法と、アトキンがこれを法 60 のホイールの偶数に基づいて計算した 60 に由来します)、その結果、分数は約 0.1117010721276 になります。
   2. rが7、19、31、または43の場合、各可能な解のエントリを3 x ²  +  y ²  =  nに反転します。このステップのふるい分け範囲に対する比率としての反転操作の数は、 π √ 0.12 ^[1] × ⁠に近づきます。4/60⁠ (分数の「4」は、この二次方程式で処理される 4 つの法と、アトキンがこれを法 60 のホイールの偶数に基づいて計算した 60 に由来します)、その結果、分数は約 0.072551974569 になります。
   3. rが 11、23、47、または 59 の場合、 x  >  yのときに、各可能な解のエントリを3 x ²  −  y ²  =  nに反転します。このステップのふるい分け範囲に対する比率としての反転操作の数は、√ 1.92 ln( √ 0.5 + √ 1.5 ) ^[1] × ⁠ に近づきます。4/60⁠ (分数の「4」は、この二次方程式で扱われる 4 つの法と、アトキンがこれを法 60 のホイールの偶数に基づいて計算した 60 に由来します)、その結果、分数は約 0.060827679704 になります。
   4. r が他の何かである場合は、完全に無視します。
4. ふるいリストの最も小さい番号から始めます。
5. ふるいリストの中でまだ素数としてマークされている次の数字を取ります。
6. 結果リストに番号を含めます。
7. 数を二乗し、その二乗の倍数すべてを非素数としてマークします。2、3、または 5 で因数分解できる倍数は、最終的な素数の列挙では無視されるため、マークする必要がないことに注意してください。
8. 手順4から7を繰り返します。ふるい分け範囲の比として素数の平方をマークするこれらの繰り返しの操作の合計数は、素数の逆数の平方の合計であり、これは素数ゼータ関数（2）の0.45224752004に近づきます...マイナス⁠1/2 ²⁠、⁠1/3 ²⁠、および⁠1/5 ²⁠ホイールによって除去された素数については、その結果に⁠を掛けます。16/60⁠範囲ごとのホイールヒットの比率。この比率は約 0.01363637571 になります。

上記の操作の比率を合計すると、上記のアルゴリズムは、ふるい分け範囲に対する反転/マーキング操作の一定の比率を約 0.2587171021... とします。アルゴリズムの実際の実装では、ふるい分け範囲が 67 と低い場合、比率は約 0.25 です。

以下は、アトキンのアルゴリズム 3.1、3.2、3.3 ^[1]を組み合わせた擬似コードです。アルゴリズムに従って、素数 2、3、5 の倍数を除く、60 を法とするすべての数値の組み合わせセット "s"を使用して、ホイールのオプションのビット パッキングをサポートするアルゴリズムの簡単なバージョンを作成します。参照されている論文では具体的には言及されていませんが、この擬似コードでは、明らかに奇数/偶数の x/y の組み合わせがいくつか排除され、それらの計算がいずれにしてもモジュロ テストに合格しない計算 (つまり、偶数、または 3 または 5 の倍数) を削減します。

limit ← 1000000000 // 任意の検索制限          

// アトキンアルゴリズムに従って 2/3/5 ホイールを 2 回振った場合のホイール「ヒット」位置のセット
s ← { 1 、7 、11 、13 、17 、19 、23 、29 、31 、37 、41 、43 、47 、49 、53 、59 }  

// 制限を含むのに十分な数のホイールでふるいを初期化します。
for n ← 60 × w + x where w ∈ { 0 , 1 ,..., limit ÷ 60 }, x ∈ s : is_prime ( n ) ← false                
      

// 候補となる素数を入力します: 
// 特定の二次形式で表現できる数が奇数である整数
。
// アルゴリズムステップ 3.1: 
n ≤ limitに対して、n ← 4 x² + y²ただしx ∈ { 1 , 2 ,...}かつy ∈ { 1 , 3 ,...} // すべての x は奇数、y はn mod 60 ∈ { 1 , 13 , 17 , 29 , 37 , 41 , 49 , 53 }の場合: is_prime ( n ) ← ¬ is_prime ( n ) // トグル状態// アルゴリズムステップ 3.2: n ≤ limitに対して、n ← 3 x² + y²ただしx ∈ { 1 , 3 ,...}かつy ∈ { 2 , 4 ,...}の場合// 奇数の x のみ、 n mod 60 ∈ { 7 , 19 , 31 , 43 } : // y が偶数の場合is_prime ( n ) ← ¬ is_prime ( n ) // 状態を切り替える// アルゴリズム ステップ 3.3: n ≤ limitの場合、n ← 3 x² - y²で、x ∈ { 2 、3 、...}かつy ∈ { x -1 、x -3 、...、1 }の場合// すべて偶数/奇数の場合n mod 60 ∈ { 11 、23 、47 、59 } : // 奇数/偶数の組み合わせis_prime ( n ) ← ¬ is_prime ( n ) // 状態を切り替える               
         
             

               
                                          
             

               
                                            
             

// ふるいにかけて合成数を除外します。ただし、ホイール上の出現部分のみです。
for n² ≤ limit 、n ← 60 × w + x where w ∈ { 0 、1 、...}、x ∈ s 、n ≥ 7 : if is_prime ( n ) : // n が素数の場合は、その平方の倍数を除外します。これで十分です。// 平方のない合成数はこのリストに載らないためです。for c ≤ limit 、c ← n² × ( 60 × w + x ) where w ∈ { 0 、1 、...}、x ∈ s : is_prime ( c ) ← false                    
     
        
        
                           
              

// 1回のスイープで、limitまでの素数の連続リストを生成します。
出力2 、3 、5 for 7 ≤ n ≤ limit 、n ← 60 × w + x where w ∈ { 0 、1 、...}、x ∈ s : if is_prime ( n ) : output n   
                   
       

この疑似コードはわかりやすくするために書かれています。奇数/偶数の x/y の組み合わせを制御することで冗長な計算がいくつか排除されていますが、それでもモジュロ テストに合格しない非生産的なループで二次計算のほぼ半分が無駄になっているため、同等のホイール因数分解された(2/3/5)エラトステネスのふるいよりも高速にはなりません。効率を改善するには、これらの非生産的な計算を最小限に抑えるか排除する方法を考案する必要があります。

このアルゴリズムは、60 を法として 2、3、または 5 で割り切れる余りを持つ数を完全に無視します。これは、60 を法としてこれら 3 つの素数のいずれかで割り切れる余りを持つ数自体がその素数で割り切れるためです。

60を法として余りが1、13、17、29、37、41、49、53となる数nはすべて、4を法として余りが1となる。これらの数は、 4 x ² + y ² = nの解の数が奇数であり、その数が平方数でない場合にのみ素数となる（ ^[1]の定理6.1として証明されている）。

60を法として余りが7、19、31、43となる数nはすべて、6を法として余りが1となる。これらの数は、 3 x ² + y ² = n^{の解の数が奇数であり、その数が平方数でない場合にのみ素数となる（ [1]}の定理6.2として証明されている）。

60を法として余りが11、23、47、59となる数nはすべて、12を法として余りが11となる。これらの数は、 3 x ² − y ² = n^{の解の数が奇数であり、その数が平方数でない場合にのみ素数となる（ [1]}の定理6.3として証明されている）。

素数候補はいずれも 2、3、5 で割り切れないので、平方数で割り切れません。これが、squarefree チェックに 2 ²、 3 ²、 5 ²が含まれない理由です。

^[1]から、上記の 3 つの二次方程式の演算はそれぞれ、範囲が無限大になるにつれて範囲の定数比となる演算数を持つことが計算できます。また、素数平方フリーカリング演算は、一定のオフセットと係数を持つ素数ゼータ関数(2) で記述できるため、範囲が無限大になるにつれて範囲の定数係数になります。したがって、上記のアルゴリズムは、O ( N ) ビットのメモリのみを使用して、 O ( N ) 回の演算でNまでの素数を計算できます。

著者らが実装したページセグメント化バージョンは、同じO ( N ) 回の演算を持ちますが、メモリ要件は、範囲の平方根以下の基数素数に必要な O ( N ^1/2 /log  N ) ビットのメモリと最小限のページバッファにまで削減されます。これは、O ( N log log  N ) 回の演算と同じ O ( N ^1/2 /log  N ) ビットのメモリ^[2]と最小限のページバッファを使用するページセグメント化されたエラトステネスのふるいと同じメモリ要件で、わずかに優れたパフォーマンスです。しかし、このようなふるいは、最大実用ホイール因数分解 (2/3/5/7 ふるいホイールと、2/3/5/7/11/13/17/19 パターンを使用したセグメント ページ バッファー内の事前カリング コンポジットの組み合わせ) を備えたエラトステネスのふるいより性能が優れているわけではありません。このふるいは、非常に大規模だが実用的な範囲ではアトキンのふるいよりもわずかに多くの操作がありますが、操作あたりの CPU クロック サイクルで Bernstein が実装したアルゴリズム間の操作時間を比較すると、操作あたりの複雑さが約 3 倍少なくなるという定数係数があります。ページ セグメント化されたアトキンのふるいの主な問題は、カリング間のスパンがページ バッファーの範囲をはるかに超えて急速に拡大するため、「素数平方のない」カリング シーケンスを実装するのが難しいことです。 Bernstein の実装では、この操作に費やされる時間は、実際の二次方程式の計算に費やされる時間の何倍にも急速に増加します。つまり、そうでなければ無視できる部分の線形複雑性が、実行時間の主な消費となるということです。したがって、最適化された実装では O(n) の時間複雑性に落ち着くかもしれませんが、操作ごとに増加するこの定数係数は、アトキンのふるいが遅くなることを意味します。

アトキンの篩の上記バージョンではない、特別に修正された「格子点の列挙」バリエーションは、理論的にはN ^{1/2 + o(1)}ビットのメモリでO ( N /log log  N )の演算を使用してNまでの素数を計算できます^[1]が、このバリエーションはほとんど実装されていません。これは、通常のページ分割バージョンや、同等だがほとんど実装されていないエラトステネスの篩バージョン (O( N ) の演算と O( N ^1/2 (log log  N )/log  N ) ビットのメモリを使用) と比較して、メモリのコストが非常に高いものの、パフォーマンスが少し向上します。^{[3] [4] [5]}

プリチャードは、ホイールふるいの場合、Big O の時間計算量を維持しながらメモリ消費量を削減できるが、これは通常、追加の計算量によって操作あたりの時間の定数係数が増加するという代償を伴うことを観察しました。したがって、この特別なバージョンは、与えられた大きな実用的なふるい範囲で費やされる実際の時間が短縮された実用的な素ふるいよりも、知的訓練としてより価値がある可能性があります。

• エラトステネスの篩
• ルジャンドルふるい
• スンダラムのふるい
• ふるい理論

• アトキンの篩とその実装に関する記事
• ふるいの最適化された実装（C）