アトキンの篩
 | この記事のほとんどまたは全てが唯一の出典にのみ基づいています。 (2024年8月) |
アトキンの篩（アトキンのふるい、英: Sieve of Atkin）とは数学において指定された整数までの素数を求めるアルゴリズムである。 古代のエラトステネスの篩が素数の倍数を取り除いていたのに比べ、アトキンの篩はいくつかの予備作業を行ってから素数の2乗の倍数を取り除いている。 2003年にA.O.L.アトキンとダニエル・バーンスタインによって発見された[1]。
アルゴリズム
[編集]アルゴリズムでの条件
- すべての余りはモジュロ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.92ln(√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となる。
出典
[編集]- ^ a b c d A.O.L. Atkin, D.J. Bernstein, Prime sieves using binary quadratic forms, Math. Comp. 73 (2004), 1023-1030.