Loading article…
数学において、エラトステネスの篩は、任意の上限までのすべての素数を見つけるための古代のアルゴリズムである。
これは、最初の素数である 2 から始めて、各素数の倍数を合成数(つまり素数ではない数) として繰り返しマークすることによって行われます。 与えられた素数の倍数は、その素数から始まる数列として生成され、それらの間の差は、その素数に等しくなります。[ 1 ]これが、試行除法を使用して各候補数を各素数で割り切れるかどうかを順次テストする方法との、この篩の重要な違いです。 [ 2 ]発見された各素数のすべての倍数が合成数としてマークされると、残りのマークされていない数は素数になります。
ふるい (古代ギリシャ語: κόσκινον Ἐρατοσθένους、kóskinon Eratosthénous )について知られている最古の言及は、ゲラサのニコマコスの算術入門[ 3 ]で、ふるいはエラトステネスの作であるとされる 2 世紀初頭の本です。紀元前 3 世紀のギリシャの数学者キレネの論文ですが、素数ではなく奇数によるふるい分けについて説明しています。[ 4 ]
素数ふるい法の一つであり、より小さな素数をすべて見つける最も効率的な方法の一つです。等差数列の素数を見つけるために使用できます。[ 5 ]
2をふるいにかけ、3をふるいにかける：エラトステネスの篩。倍数が昇華すると、残った数は素数となる。
素数とは、 1と自分自身という、ちょうど2つの異なる自然数の約数を持つ自然数のことである。
エラトステネスの方法を用いて、与えられた整数n以下のすべての素数を求めるには：
ここでの重要な考え方は、pに与えられる値はすべて素数になるということです。なぜなら、合成数であれば、他のより小さい素数の倍数としてマークされてしまうからです。なお、一部の数値は複数回マークされる可能性があります（例えば、15は3と5の両方でマークされます）。
篩の重要な特性は、加算のみが必要であり、乗算や除算は一切不要であるという点です。
改良版として、ステップ 3 でp 2から始まる数値をマークするだけで十分です。なぜなら、その時点でpのより小さい倍数はすべてマークされているからです。これは、 p 2がnより大きい場合、アルゴリズムがステップ 4 で終了できることを意味します。[ 1 ]
もう1つの改良は、最初に奇数のみ(3, 5, ..., n )をリストし、ステップ 3 で 2p ずつ増やしてカウントすることで、p の奇数倍のみをマークすることです。これは実際には元のアルゴリズムに現れます。[ 1 ] [ 4 ]これはホイール因数分解で一般化でき、最初のリストは奇数 (つまり 2 と素数) だけでなく、最初のいくつかの素数と素数でない数からのみ作成し、対応する調整された増分でカウントすることで、まず最初にそれらの小さな素数と素数でないpの倍数のみが生成されます。 [ 7 ]
30以下のすべての素数を見つけるには、次の手順に従ってください。
まず、2から30までの自然数のリストを作成します。
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30リストの最初の数字は2です。2から2ずつ増やしながら、2の次の数字を2つずつ消していきます（これらがリストにある2の倍数になります）。
2 3456789101112131415161718192021222324252627282930
リストの中で2の次の数字は3です。3から3ずつ数えて、3の次の3番目の数字を消していきます（これらがリストの中の3の倍数になります）。
2 3456789101112131415161718192021222324252627282930
リストの中で3の次にまだ消されていない数字は5です。5から5ずつ数えて（つまり5の倍数すべてを）、5の次に消していく数字をリストの中で消していきます。
2 3456789101112131415161718192021222324252627282930
リストの中で5の次に消されていない数字は7です。次のステップは、7の次にリストの中で7番目ごとの数字を消していくことですが、これらの数字（14、21、28）は7×7が30より大きいので、既にすべて消されています。リストの中でまだ消されていない数字は、30未満の素数です。
2 3 5 7 11 13 17 19 23 29エラトステネスの篩は、擬似コードで次のように表すことができます。[ 8 ] [ 9 ]
エラトステネスの篩アルゴリズムは、入力： 1より大きい 整数n。出力：2からnまでのすべての素数。 A を整数s 2 からnでインデックス付けされたブール値の配列とする。 初期設定はすべてtrueです。 i = 2, 3, 4, ..., √nを 超えない場合、A [ i ]が真であれば、j = i2 , i2 + i , i2 +2i , i2 + 3i , ... , nを超えない場合、A [ j ] := false と設定する。A [ i ]が真となるようなすべてのiを返します。
このアルゴリズムは、 nより大きくないすべての素数を生成します。一般的な最適化が含まれており、各素数iの倍数をi 2から列挙し始めます。このアルゴリズムの時間計算量はO ( n log log n )であり、[ 9 ]配列の更新がO (1)操作である場合（通常はそうである）です。
ソレンソンが指摘するように、エラトステネスの篩の問題点は、実行する演算の数ではなく、メモリ要件にある。[ 9 ] nが大きい場合、素数の範囲がメモリに収まらない可能性がある。さらに悪いことに、nが中程度であっても、キャッシュの使用は非常に非効率的である。このアルゴリズムは配列A全体を走査するため、参照の局所性はほとんどない。
これらの問題に対する解決策として、一度に範囲の一部のみをふるいにかける分割ふるいが挙げられます。 [ 10 ]これらは1970年代から知られており、次のように機能します。[ 9 ] [ 11 ]
Δを√nに選択すると、アルゴリズムの空間計算量はO ( √n )となり、時間計算量は通常の篩と同じになります。[ 9 ]
上限nが非常に大きく、エラトステネスのページ分割篩で要求される√ n未満の篩分け素数がメモリに収まらない範囲の場合、ジョナサン P. ソレンソンによって開発された擬似平方素数篩のような、より低速だがはるかにスペース効率の良い篩を代わりに使用できます。[ 12 ]
篩の増分形式[ 2 ]は、素数の生成とその倍数の生成を交互に行うことで、無限に（つまり上限なく）素数を生成します（倍数の間の隙間に素数が見つかるように）。各素数pの倍数は、素数の2乗からp（奇素数の場合は2p ）ずつ増分して直接カウントアップすることで生成されます。効率への悪影響を避けるため、生成は素数の2乗に達したときにのみ開始する必要があります。これは、データフローパラダイムの下で記号的に次のように表現できます。
primes = [ 2 , 3 , ...] \ [[ p ², p ²+ p , ...] for p in primes ],
リスト内包表記を使用して、数値の等差数列の集合減算\を表します。
素数は、素数を順番に1つずつ用いて整除性テストを繰り返し行うことで合成数をふるい分けすることによっても生成できます。これはエラトステネスの篩ではありませんが、エラトステネスの篩は合成数をテストするのではなく直接生成するにもかかわらず、しばしば混同されます。試行除算は、素数の範囲を生成する際の理論的な複雑さがエラトステネスの篩よりも劣ります。[ 2 ]
各素数をテストする際、最適な試行除算アルゴリズムではその平方根を超えないすべての素数を使用するのに対し、エラトステネスの篩では各合成数をその素因数のみから生成し、合成数の間に素数を「無料で」取得します。広く知られている1975年のデイビッド・ターナーによる関数型篩コード[ 13 ]は、エラトステネスの篩[ 7 ]の例としてよく紹介されますが、実際には最適ではない試行除算篩です。[ 2 ]
エラトステネスの篩は、コンピュータのパフォーマンスをベンチマークする一般的な方法です。[ 14 ]ランダムアクセスマシンモデルでnより小さいすべての素数を計算する時間計算量はO ( n log log n )演算であり、これは素数調和級数が漸近的にlog log nに近づくという事実の直接的な結果です。ただし、入力の長さに対して指数関数的な時間計算量を持つため、擬似多項式アルゴリズムとなります。基本アルゴリズムにはO ( n )のメモリが必要です。
このアルゴリズムのビット複雑度はO ( n ( log n ) (log log n ) )ビット演算で、メモリ要件はO ( n )です。[ 15 ]
通常実装されるページ分割バージョンは、非分割バージョンと同じO ( n log log n )の操作複雑度を持ちますが、スペース要件は、セグメントページの最小サイズと、連続するページセグメントのサイズO ( √ n / log n )から合成数をカリングするために使用される範囲の平方根より小さい基本素数を格納するために必要なメモリに削減されます。
エラトステネスの篩の特別な（実装されることはほとんどない）セグメント化バージョンは、基本的な最適化により、O ( n )回の演算とO ( √n log log n / log n )ビットのメモリを使用します。[ 16 ] [ 17 ] [ 18 ]
ビッグ O 表記法では、実用的な範囲では非常に重要になる可能性のある定数係数とオフセットが無視されます。エラトステネスの篩の変形であるプリチャードのホイール篩[ 16 ] [ 17 ] [ 18 ]はO ( n ) のパフォーマンスを持ちますが、その基本的な実装では、使用可能な範囲が利用可能なメモリの量に制限される「1 つの大きな配列」アルゴリズムを使用するか、メモリ使用量を削減するためにページ分割する必要があります。メモリを節約するためにページ分割を使用して実装した場合、基本的なアルゴリズムは依然として約O ( n / log n )ビットのメモリを必要とします ( O ( √ n / log n )ビットのメモリを使用する基本的なページ分割されたエラトステネスの篩の要件よりもはるかに多い)。プリチャードの研究は、大きな定数係数を犠牲にしてメモリ要件を削減しました。結果として得られるホイールシーブはO ( n )のパフォーマンスと許容範囲内のメモリ要件を持つが、実用的なふるい分け範囲では、エラトステネスのホイールファクタリングされた基本的なふるいよりも高速ではない。
オイラーによるゼータ積公式の証明には、合成数をそれぞれ一度ずつ消去するエラトステネスの篩のバージョンが含まれている。同じ篩は、グリースとミスラ（1978）によって再発見され、線形時間で実行されることが確認された。[ 19 ]この篩も、2からnまでの数字のリストを順番に並べたものから始まる。各ステップで、最初の要素が次の素数として識別され、リストの各要素（つまり、自身から始まる）と掛け合わされ、その結果が後で削除するためにリストにマークされる。次に、最初の要素とマークされた要素が作業シーケンスから削除され、プロセスが繰り返される。
[2] (3) 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33 35 37 39 41 43 45 47 49 51 53 55 57 59 61 63 65 67 69 71 73 75 77 79 ... [3] (5) 7 11 13 17 19 23 25 29 31 35 37 41 43 47 49 53 55 59 61 65 67 71 73 77 79 ... [4] (7) 11 13 17 19 23 29 31 37 41 43 47 49 53 59 61 67 71 73 77 79 ... [5] (11) 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 ... [...]
ここでは、アルゴリズムの最初のステップの後、奇数から始まる例を示します。したがって、k番目のステップでは、 k番目の素数の残りの倍数がすべてリストから削除され、その後は最初のk個の素数と互いに素な数のみが含まれるようになります (ホイール因数分解を参照)。これにより、リストは次の素数から始まり、最初の要素の 2 乗より小さいすべての数も素数になります。
したがって、素数の限定された数列を生成する場合、次に識別された素数が上限の平方根を超えると、リスト内の残りのすべての数が素数になります。[ 9 ]上記の例では、11 を次の素数として識別することでそれが実現され、80 以下のすべての素数のリストが得られます。
あるステップで破棄される数値は、そのステップの倍数をマークする際に引き続き使用されることに注意してください。たとえば、3 の倍数の場合は3 × 3 = 9、3 × 5 = 15、3 × 7 = 21、3 × 9 = 27、...、3 × 15 = 45、... となるため、この点には注意が必要です。[ 9 ]
primes=sieve[2..];sieve(p:nos)=p:sieve(remove(multsofp)nos);removem=filter(not.m);multsofpn=remnp==0primeswrt[x;l]=ifcar[l]modx=0thenprimeswrt[x;cdr[l]]elsecons[car[l];primeswrt[x;cdr[l]]];primes[l]=cons[car[l];primes[primeswrt[car[l];cdr[l]]]];primes[integers[2]]