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

この記事では、ある数の奇数の素因数すべての合計を、効率的に求める方法を解説します。例として n = 1092 という数を考えてみましょう。1092 を素因数分解すると 2 × 2 × 3 × 7 × 13 となり、このうち奇数の素因数は 3、7、13 です。したがって、奇数の素因数の合計は 3 + 7 + 13 = 23 となります。

この問題を解くためには、以下のルールに従います。

• 数が 2 で割り切れる間は、その因数を無視して、数を 2 で繰り返し割ります。
• この時点で数は必ず奇数になっています。3 から数の平方根までの範囲で、現在の値 i で割り切れる場合は、その因数を合計に加算し、数を i で割って処理を続けます。
• 最後に、残った数が 2 より大きい奇数であれば、それ自体が素因数であるため、合計に加算します。

より理解を深めるために、アルゴリズムを確認してみましょう。

アルゴリズム

printPrimeFactors(n):
begin
    sum := 0
    while n is divisible by 2, do
        n := n / 2
    done
    for i := 3 to √n, increase i by 2, do
        while n is divisible by i, do
            sum := sum + i
            n := n / i
        done
    done
    if n > 2, then
        if n is odd, then
            sum := sum + n
        end if
    end if
end

C++での実装例

#include<iostream>
#include<cmath>
using namespace std;
int sumOddFactors(int n){
    int i, sum = 0;
    while(n % 2 == 0){
        n = n/2; //2で割って数を小さくしていく
    }
    //ここで数は2で割り切れなくなるため、残りの因数はすべて奇数
    for(i = 3; i <= sqrt(n); i=i+2){ //iを2ずつ増やし、奇数のみを試す
        while(n % i == 0){
            sum += i;
            n = n/i;
        }
    }
    if(n > 2){
        if(n%2 == 1)
        sum += n;
    }
    return sum;
}
main() {
    int n;
    cout << "Enter a number: ";
    cin >> n;
    cout <<"Sum of all odd prime factors: "<< sumOddFactors(n);
}

実行結果

Enter a number: 1092
Sum of all odd prime factors: 23

コードのポイント

• 最初に n を 2 で割り切れなくなるまで割ることで、偶数の因数をすべて除外します。これにより、以降の処理では奇数の因数だけを考慮すればよくなります。
• ループでは i を 2 ずつ増加させることで、奇数のみを効率的に試します。
• ループ終了後に残った n が 2 より大きい場合、それは平方根以下に因数を持たない素数であるため、合計に加算します。

このアルゴリズムの計算量は O(√n) です。1 から順にすべての数で割り切れるかを調べる O(n) の方法と比べて大幅に高速であり、大きな数を扱う場合に特に有効です。