アトキンの篩（アトキンのふるい、）は、指定された整数以下の素数を列挙する素数篩の一種で、とダニエル・バーンスタインによって考案され、2004年に発表された。
エラトステネスの篩が素数の倍数を順次除去することで素数を列挙するのに対し、アトキンの篩は複数の二元二次形式による整数の表現を利用して素数候補を選び、平方因子をもつ候補を除去することで素数を列挙する。
原理 二元二次形式による素数の表現 3 より大きい素数 は以下のいずれかの二次形式で表わすことができる。
の場合： の場合： の場合： （ただし とする）
ここで、 および は正の整数である。
解の個数の偶奇性 整数 が平方因子をもたない場合、上記の条件に対応する二次形式の方程式を満たす正の整数の組 の個数が奇数であることと、 が素数であることは同値であると証明されている。
したがって、解の個数が奇数である整数を素数候補とし、偶数である整数を素数候補から除外することができる。
平方因子の除去 解の個数の偶奇性による判定は、平方因子をもたない整数（無平方数）について成り立つ。そのため、平方因子をもつ合成数を素数候補から除去する必要がある。
具体的には、すでに素数であると判定された整数の平方 の倍数を素数候補から除外する。この処理によって平方因子をもつ合成数が取り除かれ、残った素数候補は素数となる。
なお 3 以下の素数である 2 と 3 は上記の二次形式による選別の対象とならない。
アルゴリズム 前述の原理では 12 を法とした合同式で分類したが、以下のアルゴリズムの説明では原論文と同様に、さらに素数 5 を加えた 60 を法とした分類（）で行う。
アルゴリズムの前提条件 すべての余り は60を法とした剰余演算の剰余である（数 を60で割った余り）。 すべての数は、 と を含めて、正の整数である。 篩リストの項目を反転させるとは、素数か非素数かのマークを反対のマークに変えることである。
アルゴリズムの詳細
結果リストを作成して、最初の3つの素数である 2、3、5 を追加する 。 ふるい分け範囲の正の整数に対応する項目を持つ篩リストを作成する。このリストのすべての項目は、初期値として非素数とする。 篩リストの各項目番号 に対する60の剰余 において： が1, 13, 17, 29, 37, 41, 49, 53の場合、 の解の個数ごとに該当項目を反転させる。 が7,19,31,43の場合、 の解の個数ごとに該当項目を反転させる。 が11,23,47,59の場合、 のときに の解の個数ごとに該当項目を反転させる。 が他のものであれば、完全に無視すること。 篩リストの一番小さい数字から始める。 篩リストの中で、素数とマークされている次の数 を取り出す。 結果リストに数 を追加する。 数 を2乗した値 の倍数をすべて非素数としてマークする。2、3、5を因数にもつ倍数は、最終的に素数を列挙する際に除外するためマークする必要はない。 ステップ5から7を素数とマークされた数が存在する間繰り返す。
格子点列挙 上記のステップ3では方程式の解の個数を求める必要がある。アトキンとバーンスタインのアルゴリズムでは必要な格子点 を列挙するアルゴリズムが考案されている。
例えば、ステップ3.1の二次形式 については、1回の篩にかける整数の範囲を 以上 未満とすると、次の条件を満たす楕円の環状領域内（第一象限）の格子点を列挙する。
さらに、対象とする剰余 に応じて、変数 の剰余類を指定する。具体的には、 となる をもとに、、 を満たす格子点に限定する。これにより、探索する格子点の数を減らすことができる。アルゴリズムでは、楕円の環状領域の下側の境界付近から格子点を順に走査し、二次形式の値の変化分を利用して列挙を効率化している。
ステップ 3.2も、二次形式や剰余類の条件が異なるものの、基本的には同様の方法で格子点を列挙する。
ステップ 3.3では、二次形式 に対応する双曲線の帯状領域が対象となるが、こちらも格子点を順に走査するという基本的な考え方は共通している。
計算量 上記のアルゴリズムでは、3種類の二次形式について列挙される格子点の個数はいずれも篩の範囲に比例する。 また、平方因子を除去する操作の回数も篩の範囲に比例する。 このため、これらの操作回数は となる。
アトキンとバーンスタインはさらに、ホイール に限らず、求める素数の最大 とともにホイール を大きくする方法を提示し、それにより 以下の素数を 回の操作と、 ビットの記憶領域で列挙できることを示した。
注釈
出典
参考文献
関連項目 エラトステネスの篩 サンダラムの篩 篩法