数学 | しとおのはしがき

どこかおかしいエラトステネスの篩 ・1の倍数から消していく — よりもいはいいぞ(Ge|しとお) (@sitositositoo) 2018年11月19日 お久しぶりです。若干伸びたので作ってみました（これは罠で、もともと書いてたやつをちょこっと変えただけ） コード #include &lt;vector&gt; using namespace std; vector&lt;int&gt; SOE(int n) { vector&lt;bool&gt; isp(n + 1, true); int mp = 0; while (mp * mp &lt;= n) { for (int i = mp + 1; i &lt;= n + 1; i++) { if (i == n + 1) mp = n; //次の素数がない場合 if (isp[i]) { mp = i; break; } } for (int i = mp * 2; i &lt;= n; i += mp) { isp[i] = false; } } vector&lt;int&gt; ret; for (int i = 1; i &lt;= n; i++) { if (isp[i]) ret.push_back(i); } return ret; } 著作権は放棄します。 使用例 サンプルコード： #include &lt;iostream&gt; #include &lt;vector&gt; using namespace std; vector&lt;int&gt; SOE(int n) { //省略 } int main() { int n = 3141592; vector&lt;int&gt; prime = SOE(n); for (int i : prime) cout &lt;&lt; i; return 0; } 実行結果： 1 このコードのどこがいけないのか N以下の素数のリストを得られる「エラトステネスの篩」とは、次のようなアルゴリズムです（詳しくはエラトステネスの篩 - Wikipedia等を参照のこと）。 2～Nの自然数をリストアップする 2を素数認定し、2の倍数をリストから全て消していく {消されてない or 素数認定されてない}自然数の中で最小のものを素数認定（それ未満の素数では割り切れない）し、その倍数を消していく 3を繰り返し、すべての自然数が消された、または素数認定された状態になるまで続ける（具体的には、√N以下の自然数を試せば必ず終わります） 今回のコードでは自然数のリストとしてbool（真偽値）型の配列ispを使い、isp[K]をtrueからfalseにすることで「Kを消す」を表現しています。また、while文が4の操作、while内の1つ目のfor文が素数認定、2つ目のfor文が倍数消しを行っています。詳しくはコメント欄かtwitterのDMにでも。 このように対応付けすると、おかしい部分が見えてきますね。 mpの初期値を0にしている（最初の素数としてmp+1=1を認定してしまっている） 1を素数認定してしまうと、2以降のすべての自然数が倍数消しで消されてしまいますね。mpは1で初期化すべきです。 出力のfor文で、消されたかどうかの判定を1から行っている isp[0]~isp[N]までの範囲をすべてtrueで初期化しているので、1個めの修正点を直した後ここも直さないと、出力結果に1が含まれてしまいます。もちろん、isp[0]とisp[1]を最初からfalseにしておくという修正も有効です。 これらの点を修正すれば、このコードは正しく動作します。 まとめ 端っこには気をつけよう！

どこかおかしいアルゴリズム「エラトステネスの篩」