Pythonで最初のN個の自然数の積がその合計で割り切れるかを判定する方法

数値 n が与えられたとき、(1×2×…×n) の積が (1+2+…+n) の合計で割り切れるかどうかを判定する問題について解説します。

例えば、入力が num = 5 の場合を考えてみましょう。積は (1×2×3×4×5) = 120、合計は (1+2+3+4+5) = 15 となります。120 は 15 で割り切れるため、出力は True になります。

解法のアプローチ

この問題は、実際に積と合計を計算しなくても、次のシンプルな条件で判定できます。

• num + 1 が素数である場合 → False を返す
• それ以外の場合 → True を返す

なぜこの判定でうまくいくのか?

最初の n 個の自然数の積は階乗 n! であり、合計は n(n+1)/2 です。n! には n 以下のすべての整数が因数として含まれているため、合計のうち n の部分は必ず割り切れます。

ところが、n+1 が素数の場合、n! のどの因数にも n+1 は現れないため、全体として割り切れなくなります。逆に n+1 が合成数であれば、その素因数はすべて n 以下に存在するため、積は必ず合計で割り切れます。これがこの判定法の仕組みです。

実装例

以下の Python コードを実行して、動作を確認してみましょう。

def isPrime(num):
    if num > 1:
        for i in range(2, num):
            if num % i == 0:
                return False
        return True
    return False

def solve(num):
    if isPrime(num + 1):
        return False
    return True

num = 5
print(solve(num))

入力

5

出力

True

このように、素数判定と組み合わせることで、大きな n に対しても高速に答えを求めることができます。