C++ - 素因数分解！

今日は、任意の自然数を素因数分解する C++ によるアルゴリズムについてです。

まず、

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

です。そして、

• 任意の自然数を素数の積で表すことを、素因数分解という。但し、1 の素因数分解は 1 と定義する。

です。

自然数 n を素因数分解するアルゴリズムは以下のようになる。

1. n を 2 で割り切れなくなるまで、繰り返し割っていく。
   そして、割り切れるたびに 2 を表示し、n をその 2 で割った数にする。
2. 割る数を 3 として同じことを繰り返し、以降 4, 5, 6 … と続けていく。
3. 割る数を a とした時、 \(\sqrt{n} \geq a ( n \geq a^{2} )\) の間が (2) を繰り返す条件である。

素数表があれば、上記の (2) は素数だけで処理を行えばよいが、素数表は準備していないので、手当たりしだい処理を行っている。
実際、素数以外で割る場合は、それ以前にその数を素因数分解した時の素数で割り切れている(例： \(6 = 2 \times 3\) )ので、ここで割り切れる事はない。

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

0. 前提条件

• Cygwin 1.7.15
• g++ (GCC) 4.7.1

1. C++ ソース作成

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

File: prime_factorization.cpp

/*********************************************
 * 素因数分解
 *********************************************/
#include <iostream>  // for cout, cin
#include <stdio.h>   // for printf, scanf

using namespace std;

/*
 * 計算クラス
 */
class Calc
{
    // 宣言
    int a;

    public:
        // 素因数分解
        void decompositPrime(int a);
};

/*
 * 素因数分解
 */
void Calc::decompositPrime(int n)
{
    // 割る数の初期値
    a = 2;
    // √n ≧ a ( n ≧ a * a ) の間ループ処理
    while (n >= a * a) {
        // a で割り切れたら、a は素因数
        // そして、割られる数を a で割る
        // a で割り切れなかったら、 a を 1 増加させる
        if (n % a == 0) {
            printf("%d * ", a);
            n /= a;
        } else {
            a++;
        }
    }
    // 最後に残った n は素因数
    printf("%d\n", n);
}

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

    try
    {
        // 計算クラスインスタンス化
        Calc objCalc;

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

            // 素因数分解
            objCalc.decompositPrime(iNum);
        }
    }
    catch (...) {
        cout << "例外発生！" << endl;
        return -1;
    }

    // 正常終了
    return 0;
}

• Gist - C++ source code to compute prime factorizatiton.

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

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

$ g++ prime_factorization.cpp -o prime_factorization

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

3. 実行

実際に実行して素因数分解する。

$ ./prime_factorization
自然数 ( 0 : 終了 )：2
2
自然数 ( 0 : 終了 )：6
2 * 3
自然数 ( 0 : 終了 )：1200
2 * 2 * 2 * 2 * 3 * 5 * 5

---

今回のアルゴリズムも簡単すぎるアルゴリズムでした。

以上。