【C言語】ある整数の奇数の素因数の合計を効率的に求める方法

この記事では、ある整数の奇数の素因数の合計を効率的に求めるCプログラムについて解説します。

例として n = 1092 を考えてみましょう。1092 を素因数分解すると 2 × 2 × 3 × 7 × 13 となります。ここから偶数の素因数（2）を取り除いた奇数の素因数は 3, 7, 13 なので、その合計は 3 + 7 + 13 = 23 になります。

この問題を解くには、以下の手順に従います。

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

それでは、処理の流れをより深く理解するために、アルゴリズムを見ていきましょう。

アルゴリズム

sumOddFactors(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

サンプルコード

#include<stdio.h>
#include<math.h>
int sumOddFactors(int n) {
    int i, sum = 0;
    while(n % 2 == 0) {
        n = n/2; // 2で割れる限りnを2で割り続ける
    }
    // この時点でnは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;
    printf("Enter a number: ");
    scanf("%d", &n);
    printf("Sum of all odd prime factors: %d", sumOddFactors(n));
}

実行結果

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

計算量のポイント

このアルゴリズムの時間計算量は O(√n) です。まず 2 をすべて取り除いた後、3 から平方根までの奇数だけを試し割りの対象とするため、1 ずつ確認する方法よりも処理量が半分に抑えられます。さらに、平方根を超える素因数は高々 1 つしか存在しないため、ループ終了後に残った n が 2 より大きければ、それがそのまま最大の奇数の素因数として合計に加わる仕組みです。