Pythonで約数の個数が偶数か奇数かを判定する方法

ある整数 n が与えられたとき、その約数の総数が偶数か奇数かを判定することを考えます。

例えば、入力が n = 75 の場合を見てみましょう。75 の約数は [1, 3, 5, 15, 25, 75] の 6 個あるため、出力は「偶数（Even）」となります。

効率的な解法のポイント

この問題は、シンプルかつ効率的なアプローチで解くことができます。鍵となるのは、次の数学的性質です。

「約数の個数が奇数になるのは、その数が完全平方数である場合のみ」

これは、約数が通常 d と n/d のペアで現れるためです。しかし、n が完全平方数の場合、√n は自分自身とペアになるため、約数の総数が奇数になります。逆に言えば、数が完全平方数でなければ、約数の個数は必ず偶数です。

したがって、与えられた数が完全平方数かどうかを確認するだけで、「奇数（Odd）」か「偶数（Even）」かを即座に判定できます。すべての約数を列挙する必要がないため、非常に高速に動作するのが魅力です。

アルゴリズムの手順

• n < 1 の場合は処理を終了して戻る
• n の平方根を計算し、sqrt に代入する
• sqrt × sqrt が n と一致する場合、「Odd（奇数）」を返す
• それ以外の場合は、「Even（偶数）」を返す

Pythonでの実装例

def solve(n):
    if n < 1:
        return
    sqrt = n**0.5
    if sqrt*sqrt == n:
        return 'Odd'
    else:
        return 'Even'

n = 75
print(solve(n))

入力

75

出力

Even

より堅牢な実装：math.isqrt() の活用

なお、非常に大きな数を扱う場合、n**0.5 のような浮動小数点演算では誤差が生じる可能性があります。Python 3.8 以降では、math.isqrt() 関数を使うことで正確な整数の平方根を計算でき、より安全な実装が可能です。

import math

def solve(n):
    if n < 1:
        return
    sqrt = math.isqrt(n)
    if sqrt * sqrt == n:
        return 'Odd'
    else:
        return 'Even'

n = 75
print(solve(n))

この方法なら、大きな整数に対しても誤差なく完全平方数の判定が行え、約数の個数の偶奇を正確に求めることができます。