エラトステネスの篩の小噺

なんか大したことないくだらん話を書く場所が欲しかったので、くだらん話をちょいちょい思いついたら書くことにしてみます。学問的面白さは無いと思うのでお気をつけを〜。逆に競プロ知らんって人でもまあ楽しめると思います。

計算量という概念に触れ合ってから、一番驚いたのはエラトステネスの篩だったと思います。そういう人も結構いるんじゃないでしょうか。
エラトステネスの篩は、誰もが知るアルゴリズムですが、一応一言説明すると、素数の一覧を得るための高速なアルゴリズムです。時間計算量 $\Theta (N\mathrm{loglog}N))$ で、 $N$ 以下の数に対して、素数か否かを判定するようなbool配列や、 $N$ 以下の素数のリストを構築できます。これはどんぐらい早いかというと、まあほぼ線形ですね(は？)。ほぼ数数えてる間にどれが素数かわかってしまうわけです。アホ早いです。
エラトステネスの篩自体はいつ知ったか覚えてないくらい昔から知ってはいましたが、この計算量を知ったのは高3とかで、とても驚いた記憶があります。
なんで驚いたかというと、エラトステネスの篩が試し割り(素数かどうか√N以下の素数で全部割って判定する)に比べて早いという印象が全くなかったからです。試し割り法では、 $O(N\sqrt{N})$ かかるので実際にはかなり速度に違いがあります。
エラトステネスの篩の計算量を知った時は、意外だなーで終わりましたが、ふとなぜそういうことになったのか一つの説を思いついたので、ちょっと書こうと筆をとりました。

エラトステネスの篩は手でやるとマジでカス

エラトステネスの篩が手でやると如何にカスかを話していこうと思います。まず以下の図をご覧ください。

f:id:Motsu_xe:20200111170956j:plain — 金色に輝くエラトステネスの篩

まずエラトステネスの篩を実行するには、数の一覧を書かなくてはいけません。これがあまりにもだるい。どのくらいだるいかというと、30の次につい40,50,60,...と書いてしまうくらいだるいし、慌てて41,42,43,...に直したけど、よく考えたら30番台書き忘れてることに気付いて、書き直すのもだるいから隙間に書くくらいだるい。あと明らかに途中で飽きて字が崩壊して、自我崩壊しています(激ウマギャグ)。あとこれ人力にはword sizeとかいう概念無いですし、 $O(NlogN)$ なんですよね、カス。
まあ、ここまではいいでしょう。最初に1を消すのはまあいいとして、偶数を全消去します。は？？？許さん、俺がさっきまで飽きながらも頑張って書いてきた数のリストを半分も消去しやがって、ふざけるな！次に3の倍数を削除します。なんで斜めなんだよ●すぞ。30番台強引に挿入したせいで斜め崩壊してんだよおい。一行は10にするのがダメって？じゃあ何にすんだよ、次5で痛い目見るぞおい。次に5の倍数を消去します。これは癒し。最後に7の倍数を消去します。どこにあるんだよ！！！！しかももうほとんど消えてるんだよ！骨折り損のくたびれもうけだよもう、許さん！これ7の倍数だけで、線形時間かかってるよもう。実質ここで $O(N\sqrt{N}/logN)$ かかるんですよね、カス。
で、最後、素数に🙆‍♂️をします。どれが消されてんだよ！！！！！もう斜線が雑すぎてどれが消えてんだかワカンねぇよ！結局どっちかわかんなくて、これは素数だから🙆‍♂️とかやってんじゃん！篩にかけた意味さん！？！？！？！？

…とまあ如何にエラトステネスの篩がカスであるかが伝わったことでしょう。

試し割りは神

それに対して試し割りは早いんですよ。まず紙に書き出す必要がない。あと、2,3,5あたりで割れるかのチェックは頭の中ですぐできるから、除外スピードが早い。あとは素数を紙に書き出すだけ。楽チン！

なんで？

なんで試し割りのが楽なんでしょうか。それは人間はせいぜい3桁くらいまでしかやらないから、エラトステネスの篩はクソだし、試し割りは人間の素因数分解処理が十分高速に働くから早いんですよね。

でもコンピュータでは

エラトステネスの篩は実際にはクソ早いです。あと実装も楽です。
まずリストの作成がfor文で簡単にかけます、最強。さらにp個飛ばしでリストを舐める操作もfor文で簡単にできます。これはランダムアクセス様様ですね。人間には真似できん。さらに消されてるかどうかがboolで管理されてるのでとても明確でわかりやすい！いいことずくめ！だから早い！
試し割りは、人間みたいに2,3,5で割れるから飛ばすみたいのをしてくれない*1し、割り算たくさんしなきゃだから普通に遅いですね。でも人間よりめちゃくちゃ早いけどねーーーーーー！！！！！！