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

どこかおかしいエラトステネスの篩
・1の倍数から消していく

— よりもいはいいぞ(Ge|しとお) (@sitositositoo) 2018年11月19日

お久しぶりです。若干伸びたので作ってみました（これは罠で、もともと書いてたやつをちょこっと変えただけ）

コード

#include <vector>
using namespace std;

vector<int> SOE(int n) {
  vector<bool> isp(n + 1, true);
  int mp = 0;
  while (mp * mp <= n) {
    for (int i = mp + 1; i <= n + 1; i++) {
      if (i == n + 1) mp = n; //次の素数がない場合
      if (isp[i]) {
        mp = i;
        break;
      }
    }
    for (int i = mp * 2; i <= n; i += mp) {
      isp[i] = false;
    }
  }
  vector<int> ret;
  for (int i = 1; i <= n; i++) {
    if (isp[i]) ret.push_back(i);
  }
  return ret;
}

著作権は放棄します。

使用例

サンプルコード：

#include <iostream>
#include <vector>
using namespace std;

vector<int> SOE(int n) {
  //省略
}

int main() {
  int n = 3141592;
  vector<int> prime = SOE(n);
  for (int i : prime) cout << i;
  return 0;
}

実行結果：

このコードのどこがいけないのか

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にでも。

このように対応付けすると、おかしい部分が見えてきますね。