C++で数値の偶数の素因数の合計を効率的に求める方法

この記事では、C++を使用して、ある数値の偶数の素因数の合計を効率的に求める方法を解説します。まず具体例として、n = 480という数値を考えてみましょう。480の素因数は 2, 2, 2, 2, 2, 3, 5 です。ここで偶数となる素因数は2のみなので、その合計は 2+2+2+2+2 = 10 となります。

なお、素数の中で偶数なのは「2」だけであるため、この問題は実質的に「数値が2で何回割り切れるかを数え、その回数×2を求める」ことと同じです。この性質を利用すると、非常にシンプルなアルゴリズムで解くことができます。

解法のポイント

• 数値が2で割り切れる間は、その都度合計に2を加算し、数値を2で繰り返し割っていく。
• 2による割り算が終わった時点で、残りの数値は必ず奇数になります。したがって、それ以降に現れる素因数(3, 5, 7など)はすべて奇数であるため、無視して構いません。

それでは、処理の流れをより明確にするために、アルゴリズムを確認してみましょう。

アルゴリズム

sumEvenPrimeFactors(n):
begin
    sum := 0
    while n is divisible by 2, do
    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で割ってnを小さくしていく
    }
    return sum;
}
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で割り切れる限り、whileループ内で合計に2を加算し続けます。480の場合、2で5回割り切れるため、結果は10となります。ループの反復回数は2で割れる回数に依存するため、計算量はO(log n)程度と非常に効率的です。