山本隆の開発日誌

エラトステネスの篩をC++で実装してみました。

エラトステネスは、紀元前275年～紀元前194年の人です。
これほど昔の人が、こんなに優れたアルゴリズムを考え出していることに驚きます。

ソースコード中の「ステップ 1」から「ステップ 4」のコメントは、
Wikipediaのエラトステネスの篩の文章に対応しています。

//コンストラクタの引数startから始まり1ずつ増える数値を返す
struct gen1 {
  int val;
  gen1(int start) : val(start) {};
  int operator()() { return val++; };
};

int _tmain(int argc, _TCHAR* argv[])
{
  list<int> search_list(99); //探索リスト(2～100まで)
  vector<int> prime_number; //素数リスト

  //ステップ 1
  //整数を最初の素数である 2 から昇順で探索リストに羅列する。
  generate(search_list.begin(), search_list.end(), gen1(2));

  while (1)
  {
    //ステップ 2
    //リストの先頭の数を素数リストに記録する。
    int num = search_list.front();
    search_list.pop_front();
    prime_number.push_back(num);

    //ステップ 3
    //前のステップで素数リストに加えられた数の全ての倍数を、探索リストから削除する。
    search_list.erase(remove_if(search_list.begin(),
                                search_list.end(),
                                bind2nd(not2(modulus<int>()), num)),
                      search_list.end());

    //ステップ 4
    //探索リストの最大値が素数リストの最大値の平方よりも小さい場合、
    //素数リストおよび探索リストに残っている数が素数となる。
    //探索リストの最大値が素数リストの最大値の平方よりも大きい場合、
    //ステップ 2 に戻る。
    int search_max_num = *search_list.rbegin(); //探索リストの最大値
    int prime_max = *prime_number.rbegin();
    int prime_max_pow = prime_max * prime_max; //素数リストの最大値の平方
    if (search_max_num < prime_max_pow)
    {
      copy(search_list.begin(), search_list.end(), back_inserter(prime_number));
      break;
    }
  }

  //出力
  copy(prime_number.begin(), prime_number.end(), ostream_iterator<int>(cout, " "));
  return 0;
}

出力結果

2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97