Pythonで数の偶数の約数の合計を求めるプログラムの実装方法

本記事では、以下の問題文に対する解決策について学びます。

問題文

整数 n が与えられたとき、その数の偶数の約数(偶因子)の合計を求めることが課題です。

この問題を解くには、まず奇数の約数をすべて除外する必要があります。

入力された数が奇数の場合、偶数の約数は一つも存在しないため、直接 0 を返します。そうでない場合は、以下のコードで示すアプローチに従います。

アルゴリズムの考え方

このアプローチでは素因数分解を活用します。約数の合計は「各素因数の冪乗の和の積」として表せるという性質を利用します。偶数の約数のみを対象とするため、素因数 2 の部分については 2⁰(つまり 1)を除外し、2¹ 以降の項だけを合計に含めます。こうすることで、奇数の約数が自動的に排除されます。

実装例

import math
# n のすべての偶数の約数の合計を返す関数
def sumofFactors(n) :
    # n が奇数の場合
    if (n % 2 != 0) :
        return 0
    res = 1
    for i in range(2, (int)(math.sqrt(n)) + 1) :
        count = 0
        curr_sum = 1
        curr_term = 1
        while (n % i == 0) :
            count = count + 1
            n = n // i
            # ここで 2^0(=1)を除外する。それ以外の約数はそのまま扱う
            if (i == 2 and count == 1) :
                curr_sum = 0
            curr_term = curr_term * i
            curr_sum = curr_sum + curr_term
        res = res * curr_sum
    # n が素数の場合
    if (n >= 2) :
        res = res * (1 + n)
    return res
# メイン処理
n = 20
print(sumofFactors(n))

出力

36

コードの解説と検証

n = 20 の場合、約数は 1, 2, 4, 5, 10, 20 であり、このうち偶数の約数は 2, 4, 10, 20 です。これらの合計は 2 + 4 + 10 + 20 = 36 となり、出力結果と一致していることがわかります。

計算量は素因数分解のループが √n まで回るため、O(√n) となり、単純にすべての約数を列挙する方法よりも効率的です。

なお、すべての変数は下図に示すようにグローバルフレーム内で宣言されています。

まとめ

本記事では、数の偶数の約数の合計を求めるアプローチについて解説しました。素因数分解を利用することで、奇数の約数を効率的に除外しながら合計を計算できることを確認しました。同様の手法は、約数の個数や約数の積を求める問題にも応用できます。