C++ - エラトステネスのふるい！

今日は、2 以上 n 以下の自然数の中から素数を抽出（素数以外を排除）する C++ によるアルゴリズムについてです。

まず、 「自然数 p ( > 1 ) が 1 と p の他に正の約数を持たない場合、p を素数という。」 です。

そして、簡単に言うと、自然数の配列をふるいに見立てて素数以外を排除していくという方法が「エラトステネスのふるい」の考え方です。

アルゴリズムとしてまとめると、

• 2 から n のすべての自然数を「ふるい」にいれる。
• 「ふるい」の中で最小数を素数とする。
• 上記 (2) で求めた素数の倍数をすべて「ふるい」から除外する。
• 上記 (2), (3) を n まで繰り返し、「ふるい」に残った自然数が素数となる。

上記の

• 「「ふるい」に入れる」とは、 「2 から n を添え字とする配列にフラグを立てること(値を 1 に設定すること)」
• 「「ふるい」から除外する」とは、 「配列のフラグを削除すること(値を 0 に設定すること)」

で実現させています。

以下、C++ によるサンプルソースです。

記録

0. 前提条件

• Cygwin 1.7.15
• g++ (GCC) 4.7.1

1. C++ ソース作成

今回作成した C++ ソースは以下の通りです。 C++ なのでオブジェクト指向な作りにしています。 【 ファイル名： Eratosthenes.cpp 】

/*********************************************
 * エラトステネスのふるい
 *********************************************/
#include <math.h>   // for sqrt
#include <stdio.h>  // for printf, scanf

# define NUM_MAX 1000  // 最大数

using namespace std;

/*
 * 計算クラス
 */
class Calc
{
    // 宣言
    int aiPrime[NUM_MAX+1];
    int i, j, iLimit;

    public:
        // コンストラクタ
        Calc();
        // エラトステネスのふるい計算
        void calcEra();
        // コンソール出力
        void printEra();
};

/*
 * コンストラクタ
 */
Calc::Calc()
{
    // ふるいを全て 1 で初期化
    for (i = 2; i <= NUM_MAX; i++) {
        aiPrime[i] = 1;
    }
    // √NUM_MAX までチェックすればよい
    iLimit = (int)sqrt(NUM_MAX);
}

/*
 * エラトステネスのふるい計算
 */
void Calc::calcEra()
{
    // 2 以上 √NUM_MAX を超えない自然数までで判定すればよい
    for (i = 2; i <= iLimit; i++) {
        // まだふるいに残っている数について処理
        if (aiPrime[i] == 1) {
            // 自分自身は素数になるから 2 * i 番目から
            for (j = 2 * i; j <= NUM_MAX; j++) {
                // i が j で割り切れれば古いから削除
                if (j % i == 0) {
                    aiPrime[j] = 0;
                }
            }
        }
    }
}

/*
 * コンソール出力
 */
void Calc::printEra()
{
    printf("2 から %d までの素数： \n", NUM_MAX);
    for (i = 2; i <= NUM_MAX; i++) {
        if (aiPrime[i] == 1) {
            printf("%5d", i);
        }
    }
    printf("\n");
}

/*
 * メイン処理
 */
int main()
{
    try
    {
        // 計算インスタンス化
        Calc objCalc;

        // エラトステネスのふるい計算
        objCalc.calcEra();

        // コンソール出力
        objCalc.printEra();
    }
    catch (...) {
        printf("例外発生！\n");
        return -1;
    }

    // 正常終了
    return 0;
}

2. C++ ソースコンパイル

以下のコマンドで C++ ソースをコンパイルする。

$ g++ Eratosthenes.cpp -o Eratosthenes

何も出力されなければ成功です。

3. 実行

実際に実行して素数を判定する。

$ ./Eratosthenes
2 から 1000 までの素数：
    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  101  103  107  109  113
  127  131  137  139  149  151  157  163  167  173  179  181  191  193  197
  199  211  223  227  229  233  239  241  251  257  263  269  271  277  281
  283  293  307  311  313  317  331  337  347  349  353  359  367  373  379
  383  389  397  401  409  419  421  431  433  439  443  449  457  461  463
  467  479  487  491  499  503  509  521  523  541  547  557  563  569  571
  577  587  593  599  601  607  613  617  619  631  641  643  647  653  659
  661  673  677  683  691  701  709  719  727  733  739  743  751  757  761
  769  773  787  797  809  811  821  823  827  829  839  853  857  859  863
  877  881  883  887  907  911  919  929  937  941  947  953  967  971  977
  983  991  997

---

今回のアルゴリズムもよくあるアルゴリズムでした。

以上。