## 5.4 プログラム例: エラトステネスのふるい

vector の使用を示すプログラム例は、エラトステネスのふるい (The Sieve of Eratosthenes) と呼ばれる古典的なアルゴリズムで、素数を検出するために使用されます。

> 注: このプログラムのソースコードは、sieve.cpp というファイルに記述されています。

エラトステネスのふるいでは、定められた上限までのすべての番号のリストが整数ベクトルによって表現されます。基本概念は、素数とならないすべての値を取り消す (ゼロに設定) ことです。残る値はすべて素数となります。これを行うと、各値が 1 に設定されているかどうか、素数となる候補からまだ排除されていないかどうかがループによって順に検査され、すべての倍数が取り消されます。最も外側のループが終了すると、残っているすべての素数が検出されます。プログラムは次のとおりです。

    void main() {
          // 整数のふるいを作成する、初期設定
       const int sievesize = 100;
       std::vector<int> sieve(sievesize, 1);

          // 1 ビットの位置を検索する
       for (int i = 2; i * i < sievesize; i++)
          if (sieve[i])
             for (int j = i + i; j < sievesize; j += i)
                sieve[j] = 0;

          // 最後に、設定される値を出力する
       for (int j = 2; j < sievesize; j++)
          if (sieve[j])
             std::cout << j << " ";
       std::cout << std::endl;
    }

Copyright (c) 1998, Rogue Wave Software, Inc.
このマニュアルに関する誤りのご指摘やご質問は、電子メールにてお送りください。
OEM リリース, 1998 年 6 月