C++ - 素数判定！

今日は、任意の自然数が素数か否かを判定する C++ によるアルゴリズムについてです。

まず、

• 自然数 p ( > 1 ) が 1 と p の他に正の約数を持たない場合、p を素数という。

単純に考えると、

• 与えられた自然数 p が素数であるか否かを判定するには、2 から p まで順に割ってみて割り切れる自然数が存在しないか否かを判断すればよい。

となります。

しかし、それではあまりに効率が悪い事はすぐに分かると思います。

たとえば、自然数 49 が与えられた場合、8 以上の数は確認する必要はありません。2 から割ってみて 7 (= \(\sqrt{49}\)) で結果が分かります。

別の例として、33 (= \(3 \times 11\)) を考えてみると、33 を 2 から 32 まで調べなくても、\(\sqrt{33} (= 5.744\cdots)\) までの自然数で確認すればよいのです。 \(\sqrt{33}\) までの自然数に小さいほうの 3 が登場するからです。

まとめると、

• 与えられた自然数 p が素数であるか否かを判定するには、2 から \(\sqrt{p}\) までの自然数で割ってみて割り切れる自然数が存在しないか否かを判断すればよい。

ということになります。（このことが正しいか否かの数学的な証明はここではしません）

さらには、「与えられた自然数が偶数（2 の倍数）なら素数ではない」ことから、最初から奇数だけで割ってみるという考え方もあります。

しかし、そう考えるとなると 2 の倍数ばかりでなく全ての素数の倍数についても同じことを考えなければならないのでは？となるので、ここではそのような考え方はしません。

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

記録

0. 前提条件

• Cygwin 1.7.15
• g++ (GCC) 4.7.1

1. C++ ソース作成

今回作成した C++ ソースは以下の通りです。 C++ なのでオブジェクト指向な作りにしています。

File: prime_number.cpp

/*********************************************
 * 素数判定
 *********************************************/
#include <iostream>  // for cout, cin
#include <math.h>    // for sqrt
//#include <stdio.h> // for printf, scanf

using namespace std;

/*
 * 計算クラス
 */
class Prime
{
    // 宣言
    int i, iLimit;

    public:
        // 素数判定
        bool isPrime(int a);
};

/*
 * 素数判定
 */
bool Prime::isPrime(int a)
{
    // 1 は素数でない
    if (a == 1) return false;

    // 2 から √a を超えない整数までループ処理
    iLimit = (int)sqrt(a);
    for (i = 2; i <= iLimit; i++) {
        // 途中割り切れたらブレーク
        if (a % i == 0) break;
    }

    // 最後までループしきったら
    // 約数がなかったということで素数と判定
    if (i == iLimit + 1) {
        return true;
    } else {
        return false;
    }
}

/*
 * メイン処理
 */
int main()
{
    int  iNum;
    bool bPrime;

    try
    {
        // 素数クラスインスタンス化
        Prime objPrime;

        while (1) {
            // 自然数入力
            cout << "自然数 ( 0 : 終了 )：";
            cin  >> iNum;
            if (cin.fail()) break;
            if (iNum < 1) break;

            // 素数判定
            bPrime = objPrime.isPrime(iNum);
            if (bPrime) {
              cout << iNum << " : 素数" << endl;
            } else {
              cout << iNum << " : 素数ではない" << endl;
            }
        }
    }
    catch (...) {
        cout << "例外発生！" << endl;
        return -1;
    }

    // 正常終了
    return 0;
}

• Gist - C++ source code to judge prime number.

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

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

$ g++ prime_number.cpp -o prime_number

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

3. 実行

実際に実行して最大公約数を計算する。

$ ./prime_number
自然数 ( 0 : 終了 )：4
4 : 素数ではない
自然数 ( 0 : 終了 )：7
7 : 素数
自然数 ( 0 : 終了 )：95867461
95867461 : 素数

---

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

以上。