N番目の素数を求める - すぎゃーんメモ

SNSなどで話題になっていたので調べてみたら勉強になったのでメモ。 環境 Pythonでの実装例 例1 例2 例3 エラトステネスの篩 Rustでの実装例 試し割り法 エラトステネスの篩 アトキンの篩 おまけ: GMP Benchmark 高速化のテクニック 上限個数を見積もる Wheel factorization オチ Repository References 環境 手元のMacBook Pro 13-inchの開発機で実験した。 2.8 GHz Intel Core i7 16 GB 2133 MHz LPDDR3 Pythonでの実装例 例1 最も単純に「2以上p未満のすべての数で割ってみて余りが0にならなかったら素数」とする、brute force 的なアプローチ。 import cProfile import io import pstats import sys def m

[sugyan]

書いた

[studio3104]

ベンチマークによる事実の積み重ねとそれを踏まえた考察。素数を求める必要があって困ったときにまた読む...

[kaputte]

アトキンのふるいは知らなかった

[yosuke_furukawa]

へーって思って調べたらアトキンの他にもブルンの篩、サンダラムの篩、と篩法がたくさんあって素数判定の歴史を垣間見てしまった。

[als_uz]

アトキンの篩は初めて聞いた、原理調べてみよう

[aya_momo]

エラトステネスの篩を範囲をずらしながらやる。1～N、N+1～2N、…。

[collectedseptember]

素数1万個で10万ちょっとなのか。

[odakaho]

“エラトステネスの篩よりアトキンの篩の方が速いのでそれを使おう”

[miau]

primal の説明に「cache-friendly」って書かれてて、アルゴリズムが優れてるのかキャッシュが効いているのかはちょっと気になる/ベンチの「+/-」が部分がそんなに大きくないからキャッシュではないのかな

[pendamadura]

なんで先に大量に判別したほうが早いのかと思ったら列挙するというより区切って倍数を消してるのね

[KullbackLeibler]

個性がない

[yhara]

“とこのように、エラトステネスの篩を使う手法にも様々な最適化の手段があり、それらを盛り込んでいると思われる primal というcrateがあります”

[blueboy]

　よく調べましたね。　ありがとう。

[mohno]

「エラトステネスの篩」←フラグで管理しないパターンなんてはじめて見た。「アトキンの篩」←知らなかったが、オーダーは変わらないような気が。

[cj3029412]

すきすきー😺💗