素数の列挙 (JavaScript)
前にもやったけど
エラトステネスの篩をビットリストを使わないようにやってみたら、そこそこ気持ち悪い実装になったので、ここに残しておく。
下記コード中の Primes(max) 関数が max 以下の素数を小さい方から列挙する。
Primes はジェネレータなので Primes(Infinity); としてもよい。(というか max 自体取っ払ってもよかった)
数の大きさ的には Gaps の n * (n - 1) - 1 あたりがボトルネックなので、メモリ消費と処理時間を考えなければ Math.sqrt(Number.MAX_SAFE_INTEGER) あたりまで列挙できるはず。
Paiza.io ⇒ _ttps://paiza.io/projects/IG6vs6022qrOnxqX9u1mQw
Paiza.io ⇒ https://paiza.io/projects/efEgQU8Kdcy8Jp6roaOj4Q
コード:
function* Endless(v) { for (; ; ) { yield v; } } function* Repeat(v, n) { for (var i = 0; i < n; i++) { yield v; } } function* Gaps(n) { yield n * (n - 1) - 1; yield* Endless(n - 1); } function* Sieve(gaps) { for (; ; ) { yield* Repeat(1, gaps()); yield 0; } } function Supplier(e) { return () => e.next().value; } function Both(a, b) { return () => a() & b(); } function* Primes(max) { var s = () => 1; for (var n = 2; n <= max; n++) { if (s()) { s = Both(s, Supplier(Sieve(Supplier(Gaps(n))))); yield n; } } } for (var n of Primes(100)) { console.log(n); }
出力:
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97