Pythonで数の奇数の約数（奇因子）の合計を求めるプログラム

この記事では、「整数 n が与えられたとき、その数の奇数の約数（奇因子）の合計を求める」という問題の解き方を解説します。

問題文

整数 n が入力として与えられます。求めるのは、n の奇数の約数をすべて足し合わせた値です。

例えば n = 27 の場合、約数は 1, 3, 9, 27 のすべてが奇数であるため、合計は 1 + 3 + 9 + 27 = 40 となります。

アプローチのポイント

この問題で最初に行うべきは、偶数の約数をすべて除外することです。

偶数の約数を取り除くには、n が 2 で割り切れなくなるまで繰り返し 2 で割ります。この操作によって n から 2 の因数が完全に取り除かれ、それ以降に現れる約数はすべて奇数になります。

その後、残った数を素因数分解し、約数の和の公式を利用することで、奇数の約数の合計を効率よく計算できます。

アルゴリズムの手順

1. n が 2 で割り切れる間、n を 2 で割り続けます。
2. 3 以上 √n 以下の各整数 i について、i で割り切れる間 n を割りながら、等比級数の和（1 + i + i² + …）を計算し、結果に掛け合わせます。
3. ループ終了後に残った n が 2 以上であれば、それは素数なので (1 + n) を結果に掛けます。

実装例

import math

def sumofoddFactors(n):
    # 偶数の約数を除外するため、2 のべき乗をすべて取り除く
    while n % 2 == 0:
        n = n // 2

    res = 1
    # 残った奇数の素因数ごとに約数の和を計算
    for i in range(3, int(math.sqrt(n)) + 1):
        curr_sum = 1
        curr_term = 1
        while n % i == 0:
            n = n // i
            curr_term *= i
            curr_sum += curr_term
        res *= curr_sum

    # ループ後に残った n が素数の場合
    if n >= 2:
        res *= (1 + n)
    return res

# メイン処理
n = 27
print(sumofoddFactors(n))

出力

40

コードの解説

n = 27 は 3³ と素因数分解できます。i = 3 のループでは curr_term が 3 → 9 → 27 と更新され、curr_sum は 1 + 3 + 9 + 27 = 40 となり、これがそのまま答えになります。

なお、一般的に紹介されている元のコードでは return 文が if ブロック内に置かれているため、n が 1 になった場合に None が返される不具合があります。上記の実装では return 文を関数の最後に移動し、どんな入力でも正しく結果を返すように修正しています。

別のシンプルな実装

素因数分解を使わず、√n までの約数を列挙して奇数だけを加算する方法もあります。コードは直感的ですが、計算量は O(√n) で変わりません。

def sumofoddFactorsSimple(n):
    total = 0
    i = 1
    while i * i <= n:
        if n % i == 0:
            if i % 2 == 1:          # 小さい方の約数が奇数
                total += i
            pair = n // i           # 対になる約数
            if pair != i and pair % 2 == 1:
                total += pair
        i += 1
    return total

print(sumofoddFactorsSimple(27))  # 40

まとめ

この記事では、数の奇数の約数の合計を求める方法を学びました。ポイントは、まず 2 で割り切れる限り割って偶数の約数を排除し、その後、素因数分解と約数の和の公式を組み合わせて効率的に計算することです。