読む 編集 履歴表示

アトキンの篩

ウィキペディアから、無料の百科事典

アトキンの篩（アトキンのふるい、英: Sieve of Atkin）とは数学において指定された整数までのすべての素数を求めるアルゴリズムである。 古代のエラトステネスの篩が素数の倍数を取り除いていたのに比べ、アトキンの篩はいくつかの予備作業を行ってから素数の2乗の倍数を取り除いている。 2003年にA.O.L.アトキン（英語版）とダニエル・バーンスタインによって考案された[1]。

アルゴリズム

アルゴリズムの前提条件：

  • すべての余り r は60を法とした剰余演算の剰余である（数 n を60で割った余り）。
  • すべての数は、x と y を含めて、正の整数である。
  • 篩リストの項目を反転させるとは、素数か非素数かのマークを反対のマークに変えることである。
  • 対応する方程式の解の個数が奇数である数 n は素数の可能性があり（無平方数であれば素数）、解の個数が偶数である数 n は合成数である。

アルゴリズムの詳細：

  1. 結果リストを作成して、最初の3つの素数である 2、3、5 を追加する。
  2. ふるい分け範囲の正の整数に対応する項目を持つ篩リストを作成する。このリストのすべての項目は、最初は非素数（合成数）とマークする。
  3. 篩リストの各項目番号 n に対する60の剰余 r において：
    1. r が1, 13, 17, 29, 37, 41, 49, 53の場合、4x2 + y2 = n の解の個数ごとに該当項目を反転させる（結果として解の個数が奇数であれば反転、偶数であれば変化なしとなる。以下同様）。
    2. r が7,19,31,43の場合、3x2 + y2 = n の解の個数ごとに該当項目を反転させる。
    3. r が11,23,47,59の場合、x > y のときに 3x2 - y2 = n の解の個数ごとに該当項目を反転させる。
    4. r が他のものであれば、完全に無視すること。
  4. 篩リストの一番小さい数字から始める。
  5. 篩リストの中で、素数とマークされている次の数 n を取り出す。
  6. 結果リストに数 n を追加する。
  7. 数 n を2乗した値 n2 の倍数をすべて非素数としてマークする。2、3、5を因数にもつ倍数は、最終的に素数を列挙する際に除外するためマークする必要はない。
  8. ステップ5から7を繰り返す。

計算コスト：

  • ステップ 3.1 のふるい分け範囲に対する反転操作の回数比率は、4√π/15[1] × 8/60 （分子の「8」は、この2次関数が対象とする8つの剰余に由来し、分母の「60」はAtkinが60を法としたホイールに基づいて計算したことに由来する）に近づき、約0.1117010721276...となる。
  • ステップ 3.2 のふるい分け範囲に対する反転操作の回数比率は、π√0.12[1] × 4/60（分子の「4」はこの2次関数が対象とする4つの剰余に由来し、分母の「60」はAtkinが60を法としたホイールに基づいて計算したことに由来する）に近づき、結果その比率は約0.072551974569...となる。
  • ステップ 3.3 のふるい分け範囲に対する反転操作の回数比率は、√1.92ln(√0.5+√1.5)[1] × 4/60（分子の「4」はこの2次関数が対象とする4つの剰余に由来し、分母の「60」はAtkinが60を法としたホイールに基づいて計算したことに由来する）、これは約0.060827679704...となる。
  • ステップ 7 の繰り返しによる素数の二乗をマークする操作の総回数は、ふるい分け範囲の比率に対して素数の逆数の平方の合計に相当し、これは素数ゼータ関数（英語版） P(2) = 0.45224752004... から、ホイール法（英語版）によって除外された素数に対する 1/22、1/32、1/52 を引いたものとなり、その結果をふるい分け範囲あたりのホイール法の該当箇所の割合である 16/60 を掛けたものになる。これにより、約0.01363637571...の比率が得られる。

上記の各操作の比率を合計すると、このアルゴリズムにおける反転/マーク操作の割合は、ふるい分け範囲に対して約0.2587171021...と一定になる。実際のアルゴリズムの実装では、ふるい分け範囲が67と小さい場合でもその比率は約0.25となる。

出典

  1. 1 2 3 4 Atkin & Bernstein 2004.

参考文献

  • Atkin, A.O.L.; Bernstein, D.J. (2004). “Prime sieves using binary quadratic forms”. Math. Comp. 73: 1023-1030. doi:10.1090/S0025-5718-03-01501-1. https://pubs.ams.org/MCOM/2004-73-246/S0025-5718-03-01501-1. 

関連項目

関連記事

エラトステネスの篩サンダラムの篩篩法