はてなブックマーク

はじめに エラトステネスの篩とは、$n$ 以下の自然数について素数判定表を生成するアルゴリズムです。 計算量 $O(n\log\log n)$ で1予め表を生成してしまえば $1<k\le n$ の範囲の整数は定数時間で判定が行えるので、一定の範囲の整数について大量に素数判定を行う場合（素数の個数を数える、素因数分解を行うなど）は個々の数を素数判定するのに比べ非常に高速になります。 しかし、この $O(n\log\log n)$ という計算量は素数の逆数の総和が $O(\log\log n)$ に漸近していくという定理を用いているなど、かなり非直感的です。 本記事では計算量の実験的な確認を行うとともに他のアルゴリズムとの比較を行いました。2 手法 エラトステネスの篩のPythonによる実装 エラトステネスの篩の基本的なアルゴリズムは擬似コードで以下のように書けます。

注意事項 $\rm\TeX$は2019年6月9日現在，AtCoderのジャッジシステムには含まれていません．手元の処理系で動作を確認しています． 11問中 6 8問しか解けていません．今後随時追加の予定． 東大TeX愛好会@ut_tex_clubさんからの情報提供により全問解決できました．感謝です． 更新履歴 2019/06/08 #0, #1, #2, #4, #5, #8 公開 2019/06/09 #3, #6 追加 2019/06/25 ログ出力に関する情報について追記 2019/09/26 東大TeX愛好会@ut_tex_clubさんからの情報提供により #7, #9, #10を追加 まえがき $\rm\TeX$はプログラミング言語．ならば競プロするしかない． ということで解いてみました． 競プロ入門といえばおなじみの @drken さんの記事，AtCoder に登録したら次にや