C++で数値の最大の素因数を求める方法

ある整数 x が与えられたとき、その最大の素因数を求めることを考えます。例えば、x = 6 の場合、6 を素因数分解すると 2 × 3 となるため、最大の素因数は 3 です。

この問題は、対象の数を小さい約数から順に割り続けて素因数分解を行い、その過程で現れる素因数のうち最も大きいものを記録していくことで解くことができます。

アルゴリズムの流れ

1. n が偶数である限り 2 で割り続け、素因数として 2 を記録します。
2. 3 から √n までの奇数 i について、n が i で割り切れる限り割り続け、i を素因数として記録します。
3. ループ終了後も n が 2 より大きければ、残った n 自体が素数なので、それが最大の素因数となります。

√n まで調べれば十分なのは、n の約数の組のうち片方が必ず √n 以下になるためです。この工夫により、計算量を O(√n) に抑えることができます。

C++による実装例

#include <iostream>
#include<cmath>
using namespace std;
long long getMaxPrimefactor(long long n) {
    long long maxPF = -1;
    while (n % 2 == 0) {
        maxPF = 2;
        n /= 2;
    }
    for (int i = 3; i <= sqrt(n); i += 2) {
        while (n % i == 0) {
            maxPF = i;
            n = n / i;
        }
    }
    if (n > 2)
    maxPF = n;
    return maxPF;
}
int main() {
    long long n = 162378;
    cout << "Max Prime factor of " << n << " is " << getMaxPrimefactor(n);
}

実行結果

Max Prime factor of 162378 is 97

この例では、162378 は 2 × 3³ × 31 × 97 と素因数分解できるため、最大の素因数は 97 となり、プログラムの出力と一致しています。