C++プログラムで数値の偶数の約数の合計を求める方法

このプログラムは、与えられた整数のすべての偶数の約数を見つけ、それらの合計を計算して画面に出力するものです。

実行例

入力 : 30
偶数の約数 : 2+6+10+30 = 48
出力 : 48

この問題を解くアプローチは、大きく分けて2つあります。

方法1：すべての約数を列挙して偶数のみを合計する

まず対象の数値の約数をすべて求め、その中から偶数のものだけを取り出して合計します。この方法はシンプルで理解しやすい一方、約数を1つずつ確認するため、数値が大きくなると計算量が増えるという欠点があります。

方法2：素因数分解の公式を利用する

より効率的なのが、素因数分解を利用した数学的な公式を使う方法です。約数の総和は、次の式で表されます。

約数の総和 = (1 + d11 + d12 … d1a1) × (1 + d21 + d22 … d2a2) × ……… × (1 + dk1 + dk2 … dkak)
ここで di ＝ 素因数、ai ＝ di の指数（べき乗）

今回必要なのは偶数の約数だけです。したがって、元の数値が奇数の場合は偶数の約数が1つも存在しないため、その場合は0を出力します。

C++サンプルコード

#include <iostream>
#include <math.h>
using namespace std;
int main() {
    int n = 12;
    int m = n;
    if (n % 2 != 0) {
        cout << "The sum of all even factors of " << n << " is " << 0;
        return 0;
    }
    int evfac = 1;
    for (int i = 2; i <= sqrt(n); i++) {
        int count = 0, curr_sum = 1, curr_term = 1;
        while (n % i == 0) {
            count++;
            n = n / i;
            if (i == 2 && count == 1)
                curr_sum = 0;
            curr_term *= i;
            curr_sum += curr_term;
        }
        evfac *= curr_sum;
    }
    if (n >= 2)
        evfac *= (1 + n);
    cout << "The sum of all even factors of " << m << " is " << evfac;
    return 0;
}

出力結果

The sum of all even factors of 12 is 24

プログラムの解説

このコードでは、まず入力された数値が奇数かどうかを判定します。奇数であれば偶数の約数は存在しないため、0を出力して処理を終了します。

偶数の場合は、2から√nまでの範囲で素因数分解を行い、各素因数ごとの約数の和（等比級数の和）を計算します。それらを掛け合わせることで、全体の約数の総和が得られます。ここでのポイントは、素因数2を処理する際に級数の先頭にある「1」を除外している点です。これにより、奇数の約数が合計に含まれるのを防ぎ、偶数の約数のみの合計を正しく求められます。

たとえば n = 12 の場合、12の約数は 1, 2, 3, 4, 6, 12 であり、このうち偶数は 2, 4, 6, 12 です。したがって、合計は 2+4+6+12 = 24 となり、プログラムの出力と一致します。