mk-mode BLOG

このブログは自作の自宅サーバに構築した Debian GNU/Linux で運用しています。
PC・サーバ構築等の話題を中心に公開しております。(クローンサイト: GitHub Pages

ブログ開設日2009-01-05
サーバ連続稼働時間
Reading...
Page View 合計
Reading...
今日
Reading...
昨日
Reading...

C++ - 素因数分解!

[ プログラミング, 数学 ] [ C言語 ]

こんばんは。

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

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

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

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

  • n を 2 で割り切れなくなるまで、繰り返し割っていく。 そして、割り切れるたびに 2 を表示し、n を 2 で割った数にする。
  • 割る数を 3 として同じことを繰り返し、以降 4, 5, 6 ・・・と続けていく。
  • 割る数を a とした時、√n ≧ a ( n ≧ a * a ) の間が (2) を繰り返す条件である。

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

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

記録

0. 前提条件

  • Cygwin 1.7.15
  • g++ (GCC) 4.7.1

1. C++ ソース作成

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
/*********************************************
 * 素因数分解
 *********************************************/
#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;
}

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

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

1
$ g++ PrimeDecomposition.cpp -o PrimeDecomposition

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

3. 実行

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

1
2
3
4
5
6
7
$ ./PrimeDecomposition
自然数 ( 0 : 終了 ):2
2
自然数 ( 0 : 終了 ):6
2 * 3
自然数 ( 0 : 終了 ):1200
2 * 2 * 2 * 2 * 3 * 5 * 5

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

以上。

Comments