この記事は? インターネット上でエラトステネスの篩の実装を検索すると、かなりの割合で、エラトステネスの篩とよんでいいのか怪しい「似非エラトステネスの篩」とでも称すべきものがみられます。 この記事では、「試し割り」「似非エラトステネスの篩」「エラトステネスの篩」の3つのアルゴリズムを比較して、その違いを解説します。 3つのアルゴリズムの比較 1. 試し割り 実装 まず他のアルゴリズムに対する評価基準として、試し割りのアルゴリズムを示します。 試し割りは、nが素数であるかを判定するために\sqrt{n}以下の全ての素数で割って確認するアルゴリズムです。 import sys # limit 以下の全ての素数を返す def list_primes(limit): primes = [] for i in range(2, limit + 1): is_prime = True for p in
![本当は遅い「似非エラトステネスの篩」の罠](https://cdn-ak-scissors.b.st-hatena.com/image/square/bb5cd465de61cdd3968368bf848f37423eacd31d/height=288;version=1;width=512/https%3A%2F%2Fres.cloudinary.com%2Fzenn%2Fimage%2Fupload%2Fs--nCvizWW0--%2Fc_fit%252Cg_north_west%252Cl_text%3Anotosansjp-medium.otf_55%3A%2525E6%25259C%2525AC%2525E5%2525BD%252593%2525E3%252581%2525AF%2525E9%252581%252585%2525E3%252581%252584%2525E3%252580%25258C%2525E4%2525BC%2525BC%2525E9%25259D%25259E%2525E3%252582%2525A8%2525E3%252583%2525A9%2525E3%252583%252588%2525E3%252582%2525B9%2525E3%252583%252586%2525E3%252583%25258D%2525E3%252582%2525B9%2525E3%252581%2525AE%2525E7%2525AF%2525A9%2525E3%252580%25258D%2525E3%252581%2525AE%2525E7%2525BD%2525A0%252Cw_1010%252Cx_90%252Cy_100%2Fg_south_west%252Cl_text%3Anotosansjp-medium.otf_37%3A%2525E3%252582%252584%2525E3%252581%25258D%2525E3%252581%25259D%2525E3%252581%2525B0%2525E3%252581%25258F%2525E3%252581%252598%2525E3%252582%252589%252Cx_203%252Cy_121%2Fg_south_west%252Ch_90%252Cl_fetch%3AaHR0cHM6Ly96ZW5uLWRldi5naXRodWIuaW8vZGVmYXVsdC1hdmF0YXJzL2Rhcmsvbi5wbmc%3D%252Cr_max%252Cw_90%252Cx_87%252Cy_95%2Fv1627283836%2Fdefault%2Fog-base-w1200-v2.png)