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

はじめに

正の整数 n が与えられたとき、「n そのもの」と「n の最大素因数」の合計を求める問題を考えてみましょう。例えば、数が 26 の場合、26 を素因数分解すると 2 × 13 となるため、最大素因数は 13 です。したがって、求める合計は 26 + 13 = 39 となります。

アルゴリズムの考え方

アプローチはとてもシンプルです。

1. 対象の数を素因数分解し、最大の素因数を見つける
2. 元の数と最大素因数を足し合わせる
3. 結果を返す

最大素因数の効率的な求め方

すべての約数を総当たりで調べると非効率ですが、以下の手順に従えば O(√n) 程度の計算量で最大素因数を求められます。

• まず、数が 2 で割り切れる間は 2 で割り続けます(偶数の素因数をすべて除去)。
• 次に、3 から √n までの奇数について、割り切れる間は順に割っていきます。
• ループ終了後に残った数が 2 より大きければ、それ自体が最大の素因数です。

サンプルコード

#include<iostream>
#include<cmath>
using namespace std;

// 最大素因数を求める関数
int maxPrimeFact(int n){
    int maxPrime = -1;
    // 2で割れるだけ割る
    while (n % 2 == 0) {
        maxPrime = 2;
        n /= 2;
    }
    // 3から√nまでの奇数で割る
    for (int i = 3; i <= sqrt(n); i += 2) {
        while (n % i == 0) {
            maxPrime = i;
            n = n / i;
        }
    }
    // 残った数が2より大きければ、それが最大素因数
    if (n > 2)
        maxPrime = n;
    return maxPrime;
}

// 数と最大素因数の合計を返す関数
int getRes(int n) {
    int sum = maxPrimeFact(n) + n;
    return sum;
}

int main() {
    int n = 26;
    cout << "Sum of " << n << " and its max prime factor is: " << getRes(n);
}

実行結果

Sum of 26 and its max prime factor is: 39

コードのポイント

• maxPrimeFact 関数: 引数として受け取った数を素因数分解し、最も大きな素因数を返します。最初に 2 を処理することで、以降は奇数のみを調べればよくなります。
• getRes 関数: 元の数 n と最大素因数を加算し、合計を返します。
• sqrt(n) まで調べる理由: √n を超える約数の組合わせは存在しないため、そこで探索を打ち切っても見落としがありません。これにより処理が高速化されます。

この手法は、大きな数に対しても比較的効率的に動作するため、競技プログラミングやアルゴリズム学習の基礎として役立ちます。