エラトステネスの篩の高速化 - Qiita

世の中に多くあるエラトステネスの篩の実装、多くあるくせにちょっとしか高速化してないのが悲しいので高速化エラトステネスの篩を書いてみることにします。 エラトステネスの篩の高速化 (1) ← 今ココ エラトステネスの篩の高速化 (2) エラトステネスの篩の高速化 (3) エラトステネスの篩の高速化 (4) エラトステネスの篩の高速化 (5) エラトステネスの篩の高速化 (6) エラトステネスの篩の高速化 (7) 問題設定 とりあえず C++11 くらいで動く物を作りたいと思います。インラインアセンブラや SIMD、並列化は明示的には入れない方針です。あと、エラトステネスの篩自体の高速化を目指すので、結果は一部の具体的な素数の確認と $\pi(x)$ の値で確認することにしますし、その時間は考慮しないことにします。 また、ライブラリ的に使えるよう、将来的には区間篩 (大きな $x$ に対して $

[runningupthathill]

触る対象を減らす、キャッシュメモリに乗るようにする、並列化可能にする、ループアンローリング…なるほど、コンピュータの仕組みと数学の両方を理解してる人の頭の中を覗くとこんな感じなのね。

[mohno]

5年前の記事か。微笑ましい話題だな、と思ったら、のっけから「std::ceil(std::sqrt(x) + 0.1);」←floorでいいだろ（今どき誤差を気にする必要があるのかというのも）

[ch1248]

エラトステネスの篩か

[kfrom40]

自分のライブラリをアップデートしておこうかな

[pekee-nuee-nuee]

す、すごい