【Python】約数の個数が偶数か奇数かを判定するプログラムの書き方

この記事では、ある整数の約数の個数が偶数か奇数かを判定するPythonプログラムについて、その考え方と実装方法をわかりやすく解説します。

問題文

ある数「n」が与えられたとき、その約数の総数が偶数であるか奇数であるかを判定してください。

例えば、n = 10 の場合、約数は 1, 2, 5, 10 の4つなので「偶数」。一方、n = 100 の場合は 1, 2, 4, 5, 10, 20, 25, 50, 100 の9つとなり「奇数」となります。

アプローチ：約数を実際に数える

最も基本的な方法は、すべての約数を見つけ、その個数が偶数か奇数かをチェックすることです。

ここで重要なのは、約数は必ずペア（i と n ÷ i）で現れるという性質です。これを利用すれば、1から √n までの範囲だけを調べるだけでよく、計算量を O(√n) に抑えられます。ただし、n が平方数の場合は i = n ÷ i となるため、そのときに限りカウントを1だけ増やします。

実装例

import math

def countDivisors(n) :
    count = 0
    # すべての約数を計算する
    root = int(math.sqrt(n)) + 2
    for i in range(1, root) :
        if (n % i == 0) :
            # 約数が等しい場合（平方数の平方根）は1を加算、それ以外は2を加算
            if (n // i == i) :
                count = count + 1
            else :
                count = count + 2

    if (count % 2 == 0) :
        print("Even")
    else :
        print("Odd")

# 動作確認用のドライバープログラム
print("The count of divisor: ")
countDivisors(100)

出力結果

The count of divisor: 
Odd

n = 100 は 10 × 10 と表せる平方数であり、約数が9個（奇数）あるため、「Odd」と出力されます。

補足：数学的な性質を使ったより簡単な判定法

実は、約数の個数が奇数になるのは「その数が完全平方数である場合」だけです。これは、約数が d と n ÷ d のペアで現れる中で、d = n ÷ d（つまり d = √n）となるケースが存在するのは平方数だけだからです。

この性質を使えば、約数を数え上げる必要すらなく、n が平方数かどうかを確認するだけで判定できます。

import math

def isPerfectSquare(n) :
    root = int(math.sqrt(n))
    return root * root == n

def checkDivisorCount(n) :
    if isPerfectSquare(n) :
        print("Odd")   # 平方数なら約数の個数は奇数
    else :
        print("Even")  # それ以外は偶数

checkDivisorCount(100)  # 出力: Odd
checkDivisorCount(10)   # 出力: Even

こちらの方法なら計算量は O(1) 相当となり、非常に大きな数でも高速に判定できます。

まとめ

この記事では、与えられた整数の約数の個数が偶数か奇数かを判定する2つの方法を紹介しました。

• 1から √n までをループして約数を数える方法（O(√n)）
• 完全平方数かどうかを判定するだけで済ませる方法（ほぼ O(1)）

競技プログラミングやアルゴリズムの学習において、約数の個数の偶奇は頻出のトピックです。「平方数だけが奇数個の約数を持つ」という性質はぜひ覚えておきましょう。