アトキンのふるい

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

アルゴリズム

アルゴリズムでは：

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

アルゴリズム:

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

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

擬似コード

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

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 のみif 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のみif n mod 60 ∈ { 7、19、31 , 43 } : // y が偶数の場合is_prime ( n ) ← ¬ is_prime ( n ) // トグル状態// アルゴリズム ステップ 3.3: for n ≤ limit 、n ← 3 x² - y² where x ∈ { 2 、3 、...} and y ∈ { x -1 、x -3 、...、1 } // すべて偶数/奇数if 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です。7 ≤ n ≤ limit 、n ← 60 × w + xです。w ∈ { 0、1 、... } 、x ∈ sの場合: is_prime ( n ) :出力n

この擬似コードは明瞭性を重視して記述されています。x / $y の$ 奇数/偶数の組み合わせを制御することで冗長な計算がいくつか削減されていますが、それでも $二$ 次方程式の計算のほぼ半分がモジュロテストに合格しない非生産的なループに費やされているため、同等のホイール分解（2/3/5）されたエラトステネスのふるいよりも高速ではありません。効率を向上させるには、これらの非生産的な計算を最小限に抑える、または排除する方法を考案する必要があります。

実装

以下はJava 内でのアルゴリズムの実装です。^{[ 2 ]}これはブール配列を使用して整数が素数かどうかをマークします。

パブリック静的リスト< int > sieveOfAtkin ( int limit ) {boolean [] arr = new boolean [ limit + 1 ] ; // デフォルトではfalseで初期化されます// 2と3を素数としてマークする制限> 2の場合、arr [ 2 ] = true ;制限> 3の場合、arr [ 3 ] = true ;// 3つの条件すべてをチェックするfor ( int x = 1 ; x * x <= limit ; x ++ ) {for ( int y = 1 ; y * y <=限界; y ++ ) {// 条件1int n = ( 4 * x * x ) + ( y * y );if ( n <=制限&& ( n % 12 == 1 || n % 12 == 5 ))arr [ n ] = ! arr [ n ] ;// 条件2n = ( 3 * x * x ) + ( y * y );もし( n <=制限&& n % 12 == 7 )arr [ n ] = ! arr [ n ] ;// 条件3n = ( 3 * x * x ) - ( y * y );もし( x > y && n <=制限&& n % 12 == 11 )arr [ n ] = ! arr [ n ] ;}}// すべての倍数をマークする// 平方数を非素数としてfor ( int i = 5 ; i * i <= limit ; i ++ ) {arr [ i ] == falseの場合、続行します。for ( int j = i * i ; j <= limit ; j += i * i )arr [ j ] =偽;}// すべての素数を格納するリスト< int >素数=新しいリスト< int > ();for ( int i = 2 ; i <= limit ; i ++ ) {もし（arr [ i ] == true ）{素数。( i )を加算します。}}素数を返します。}

説明

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

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

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

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

素数候補はどれも2、3、5で割り切れないため、その平方数でも割り切れません。そのため、スクエアフリーチェックでは2 ²、3 ²、5 ²は含まれません。

計算の複雑さ

上記の3つの二次方程式の演算はそれぞれ、範囲が無限大に近づくにつれて、演算回数が範囲の定数倍になることが計算によって分かります^{[ 1 ]} 。さらに、素数平方除去演算は、定数のオフセットと係数を持つ2における素数ゼータ関数で記述できるため、これも範囲が無限大に近づくにつれて、範囲の定数倍になります。したがって、上記のアルゴリズムは、わずかO(N)ビットのメモリで、 $O$ $($ $N$ $)$ 回の演算 $で$ $N$ $まで$ $の$ $素数を計算できます。$

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

上記のアトキンの篩とは異なる、特別に改良された「格子点の列挙」法は、理論的には $Nまでの素数を$ $O (N /log(log(N)))$ 回の演算と $N1 /2+ o (1)$ ビットのメモリで計算できるが^{[ 1 ]}、この法則はほとんど実装されていない。これは、通常のページ分割法や、同等だがほとんど実装されていないエラトステネスの篩（ $O (N)$ 回の演算と $O (N1 /2log (log(N))/log(N))$ ビットのメモリを使用する）と比較して、メモリコストが非常に高いものの、若干性能が向上する。^{[ 4 ]}^{[ 5 ]}^{[ 6 ]}

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

参照

参考文献

^ ^a ^b ^c ^d ^e ^f ^g ^h ⁱ ^j A.OL Atkin, DJ Bernstein,二元二次形式を用いた素ふるい, Math. Comp. 73 (2004), 1023-1030. [1]
^ 「アトキンのふるい」 . GeeksforGeeks . 2016年1月16日. 2025年8月21日閲覧。
^プリチャード、ポール、「線形素数ふるい：家系図」、科学、コンピュータプログラミング9：1（1987）、17–35頁。
^ポール・プリチャード「素数を見つけるための亜線形加法ふるい」Communications of the ACM 24 (1981), 18–23. MR 0600730
^ポール・プリチャード「ホイールシーブの説明」Acta Informatica 17 (1982), 477–485. MR 0685983
^ポール・プリチャード「高速コンパクト素数ふるい（その他）」『アルゴリズムジャーナル4』（1983年）、332-344頁。MR 0729229

外部リンク

[paper-1] ^ ^a ^b ^c ^d ^e ^f ^g ^h ⁱ ^j A.OL Atkin, DJ Bernstein,二元二次形式を用いた素ふるい, Math. Comp. 73 (2004), 1023-1030. [1]

[2] 「アトキンのふるい」 . GeeksforGeeks . 2016年1月16日. 2025年8月21日閲覧。

[3] プリチャード、ポール、「線形素数ふるい：家系図」、科学、コンピュータプログラミング9：1（1987）、17–35頁。

[4] ポール・プリチャード「素数を見つけるための亜線形加法ふるい」Communications of the ACM 24 (1981), 18–23. MR 0600730

[5] ポール・プリチャード「ホイールシーブの説明」Acta Informatica 17 (1982), 477–485. MR 0685983

[6] ポール・プリチャード「高速コンパクト素数ふるい（その他）」『アルゴリズムジャーナル4』（1983年）、332-344頁。MR 0729229

[

[ 2 ]

[

[ 4 ]

[ 5 ]

[ 6 ]