C++プログラムで素因数を求める方法を解説

素因数とは、ある数の約数の中で素数であるものを指します。

約数とは、掛け合わせるとその数になる整数のことです。

素因数分解とは、対象の数を素因数で再帰的に割り算を繰り返し、その数のすべての素因数を求めるプロセスのことです。

例:
N = 120
素因数 = 2, 3, 5
素因数分解: 2 × 2 × 2 × 3 × 5

素因数に関するポイント

• ある数の素因数の集合は常に一意に定まります。
• 素因数分解は、約数の判定や最小公倍数・最大公約数の計算など、多くの数学的計算において重要な役割を果たします。
• 暗号技術(RSA暗号など)の基礎となる重要な概念でもあります。

C++で素因数を求めるプログラム

以下のプログラムは、試し割り法を用いて与えられた整数の素因数をすべて出力します。まず2で割り切れる間は2を出力し、その後は3から√nまでの奇数のみを試すことで計算量を O(√n) に抑え、効率的に処理できます。

サンプルコード

#include <iostream>
#include <math.h>
using namespace std;
void printPrimeFactors(int n) {
    while (n%2 == 0){
        cout<<"2\t";
        n = n/2;
    }
    for (int i = 3; i <= sqrt(n); i = i+2){
        while (n%i == 0){
            cout<<i<<"\t";
            n = n/i;
        }
    }
    if (n > 2)
    cout<<n<<"\t";
}
int main() {
    int n = 2632;
    cout<<"Prime factors of "<<n<<" are :\t";
    printPrimeFactors(n);
    return 0;
}

実行結果

Prime factors of 2632 are : 2  2  2  7  47

この実行結果から、2632 = 2 × 2 × 2 × 7 × 47 と素因数分解できることがわかります。試し割り法はシンプルでありながら実用的なアルゴリズムで、競技プログラミングや暗号の基礎学習など、さまざまな場面で活用されています。