【C++】ある数の偶数の素因数の合計を効率的に求める方法

はじめに

この記事では、ある整数の「偶数の素因数」の合計を効率的に求める方法を解説します。例として、n = 480 という数を考えてみましょう。480 を素因数分解すると、2、2、2、2、2、3、5 となります。このうち偶数である素因数は 2 のみなので、その合計は 2+2+2+2+2 = 10 になります。

一見すると、すべての因数を列挙して偶数かどうか判定する必要があるように思えますが、実はもっとシンプルな方法で解けます。

解法のポイント

偶数の素因数は 2 しか存在しない、という点が重要です。これを利用すると、次の手順で問題を解くことができます。

• 数が 2 で割り切れる間、そのたびに合計に 2 を加算し、数を 2 で割っていく。
• 2 で割り切れなくなった時点で、その数は必ず奇数になっているため、以降に偶数の因数は現れない。したがって、残りの因数（3 や 5 など）はすべて無視してよい。

この方法なら、処理時間は 2 で割れる回数に比例するだけなので、非常に高速です（計算量は O(log n)）。

アルゴリズム

begin
    sum := 0
    n が 2 で割り切れる間、繰り返す
        sum := sum + 2
        n := n / 2
    done
end

C++での実装例

#include<iostream>
using namespace std;

int sumEvenFactors(int n){
    int i, sum = 0;
    while(n % 2 == 0){
        sum += 2;
        n = n / 2; // 2で割って数を小さくしていく
    }
    return sum;
}

int main() {
    int n;
    cout << "Enter a number: ";
    cin >> n;
    cout << "Sum of all even prime factors: "<< sumEvenFactors(n);
}

実行結果

Enter a number: 480
Sum of all even prime factors: 10

まとめ

偶数の素因数は 2 のみであることを利用すれば、数を 2 で割り続けるだけで偶数の素因数の合計を簡単に求められます。全因数を探索するアプローチと比べて計算量が大幅に少なく、大きな数でも高速に動作する実用的な手法です。