はじめに
素数を見つけるためのアルゴリズムの1つは、古代ギリシャの数学者によって提案されたエラトステネスのふるいです。
ウィキペディアの写真：
ポイントは、すでに単純であることがわかっている倍数の数を消すことです。 ストレスを受けないままにすることは簡単です。 詳細はこちら 。
ふるいを検索するときの問題の1つは、フィルター処理された数値に割り当てる必要があるメモリの量です。 削除された困難なものは削除され、メモリが削減されますが、最初は大量が必要です。
これを解決するために、セグメンテーション（メモリが断片的に割り当てられる場合）およびその他のトリック（ ここを参照）が使用されます。
アルゴリズムの実装
以下のアルゴリズム（javaで記述）は、最小量のメモリを想定しています-実際、見つかった各素数に対して、別の数を保存します-最後の1つが取り消し線（最大）になります。 メモリサイズln（n）-見つかった素数の数を正しく推定した場合。
アルゴリズムの本質：
昇順でソートされた複数の素数がすでに見つかっているとします。 （アルゴリズムは[2,3]で始まります）。 それらのそれぞれについて、最後の（最大の）取り消し線番号を保存します。 プライム自体で初期化します。
たとえば、見つかった最大の素数+1など、素数の候補を選択します（以下のアルゴリズムでは、明らかに単純ではないものでもスキップします）。
候補は、現在の素数の最後の三振と比較されます。 現在のストライクアウトは候補よりも少ないですが、現在のプライム分だけ増やします。 現在の取り消し線が候補と等しい場合、候補は素数ではありません。 次の候補を選択してください。
現在の取り消し線が候補よりも大きい場合は、次の素数の候補を確認します。
素数のリストの最後に到達した場合（つまり、すべての候補が候補よりも多く消された場合）、別の素数が見つかりました。
それをリストに追加し、見つかったシンプルによって最後に消されたものを初期化します。
Javaコード
import java.util.ArrayList; import java.util.List; public class SieveEratosthenes { static class PrimePair { Integer prime; Integer lastCrossed; PrimePair(Integer prime, Integer lastCrossed) { this.prime = prime; this.lastCrossed = lastCrossed; } } private List<PrimePair> primes; private SieveEratosthenes() { primes = new ArrayList<>(); primes.add(new PrimePair(2, 2)); primes.add(new PrimePair(3, 3)); } private void fillNPrimes(int n) { while (primes.size()<n) { addNextPrime(); } } private void addNextPrime() { int candidate = primes.get(primes.size()-1).prime + 2; for (int i = 1; i < primes.size(); i++) { PrimePair p = primes.get(i); while (p.lastCrossed < candidate) { p.lastCrossed += p.prime; } if (p.lastCrossed == candidate) { //restart candidate+=2; i=-1; } } System.out.println(candidate); primes.add(new PrimePair(candidate, candidate)); } public static void main(String[] args) { SieveEratosthenes test = new SieveEratosthenes(); test.fillNPrimes(1000); } }
同じPythonコード：
primes = [2, 3] last_crossed = [2, 3] def add_next_prime(): candidate = primes[-1] + 2 i = 0 while i < len(primes): while last_crossed[i] < candidate: last_crossed[i] += primes[i] if last_crossed[i] == candidate: candidate += 2 i = 0 i += 1 primes.append(candidate) last_crossed.append(candidate) def fill_primes(n): while len(primes) < n: add_next_prime() fill_primes(1000) print(primes)
次の候補を選択するときに、従来のホイールアルゴリズムのすべてのロジックを適用できます。
→ GitHub
おそらくこれは別の自転車の発明です。 コメントを聞く準備ができています。