アルゴリズムでの条件
すべての余りはモジュロ60の余りである(数を60で割って余りを返す)。
xとyを含むすべての数は正の整数である。
篩リストの項目を反転させるとは、素数か非素数かのマークを反対のマークに変えることである。
対応する方程式の解の数が奇数の数は素数の可能性があり(正方数でなければ素数)、解の数が偶数の数は合成の可能性がある。
アルゴリズム
2、3、5で埋め尽くされた結果リストを作成する。
各正整数のエントリを持つふるいリストを作成する。このリストのすべてのエントリは、最初は非素数(合成数)とマークされる。
篩リストの各エントリー番号nについて、モジュロ60の余りrにおいて:
rが1, 13, 17, 29, 37, 41, 49, 53の場合、4x2 + y2 = nの各解のエントリを反転させます。このステップのふるい分け範囲に対する反転操作の回数は、4√ π / 15 [ 1] × 8 / 60 (分数の「8」は、この2次関数が扱う8つのモジュロに由来し、60は、Atkinがモジュロ60の偶数の輪に基づいて計算したためです)に近づき、約0.1117010721276...となります。
rが7,19,31,43の場合、3x2 + y2 = nの各解のエントリを反転させます。このステップのふるい分け範囲に対する反転操作の回数は、π √ 0.12 [ 1] × 4 / 60 (分数の「4」はこの2次関数が扱う4つのモジュロに由来し、「60」はAtkinがモジュロ60の偶数の輪に基づいて計算したためです)に近づき、その結果、分数は約0.072551974569...となります。
rが11,23,47,59の場合、x > yのときに3x2 - y2 = nの各解の可能性のあるエントリをフリップします。このステップのふるい範囲に対するフリップ操作の数は、√ 1.92 ln(√ 0.5 +√ 1.5 )[ 1] × 4 / 60 (分数の "4 "はこの2次関数が扱う4つのモジュロに由来し、"60 "はAtkinがモジュロ60の偶数の輪に基づいてこれを計算したためである)、これは約0.060827679704...となります。
rが他のものであれば、完全に無視すること。
篩のリストの一番小さい数字から始める。
篩のリストの次の番号の素数を取る。
結果リストに番号を含める。
数を2乗し、その2乗のすべての倍数を素数でないものとしてマークする。2、3、5で因数分解できる倍数はマークする必要がないことに注意。
ステップ4から7を繰り返す。この繰り返しによる素数の平方をマークする操作の総数は、篩範囲の比率に対して素数の逆数の平方の合計に相当し、これは素数ゼータ関数(2)の0.45224752004...から、ホイールによって除外された素数に対する1 / 22 、1 / 32 、1 / 52 を引いたものに近づき、その結果を篩範囲あたりのホイールヒットの比率である16 / 60 で掛けたものになる。これにより、約0.01363637571...の比率が得られる。
上記の操作の比率を足し合わせると、上記のアルゴリズムでは、ふるい分け範囲に対する反転/マーキング操作の比率は約0.2587171021...と一定になる。実際のアルゴリズムの実装では、ふるい分け範囲が67と低い場合、比率は約0.25となる。