Python で素因数を見つける方法

Python で整数の素因数を見つけるには、その数を素数で繰り返し割ります。この記事では、カスタムの試し割り関数、エラトステネスのふるいによるアプローチ、およびサードパーティの primefac パッケージを紹介します。因数はリストとして返され、重複する因数も含まれます。

素因数分解の概要

整数の因数は、その整数を余りなく割り切ります。素数は 1 より大きく、正の因数をちょうど 2 つ（1 とその数自身）だけ持ちます。たとえば、3、7、11、13 は素数です。

素因数分解は、1 より大きい整数を素数の積として表します。6 = 2 × 3 であるため、その素因数は 2 と 3 です。因数は複数回現れることもあります。20 = 2 × 2 × 5 であるため、その素因数は [2, 2, 5] です。

Python で素因数を見つけるさまざまなアプローチ

小さく直接的な実装には試し割りを選択し、上限までの素数も必要な場合はふるいを使用し、パッケージに因数分解を任せたい場合は primefac を使用してください。以下のカスタム関数は、各素因数をその重複度とともに返します。

素因数分解を行うカスタム関数

試し割りは、候補となる約数を昇順にテストします。候補が残りの値を割り切ると、関数はそれを記録し、割り出してから再度テストします。候補の二乗が残りの値以下である間だけテストすれば十分です。より大きな因数が残っていれば、そのペアとなる因数はすでに見つかっているはずだからです。1 より大きい残りの値はすべて素数です。

整数 20 でこの例を実行してください。

def prime_factors(n):
    if n < 1:
        return None

    factors = []
    divisor = 2
    while divisor * divisor <= n:
        if n % divisor == 0:
            factors.append(divisor)
            n //= divisor
        else:
            divisor += 1
    if n > 1:
        factors.append(n)
    return factors


print(prime_factors(20))

[2, 2, 5]

この関数は 1 つの約数ループを使用し、最初に素数のリストを生成することはしません。その // 演算により、残りの値は整数のまま保たれます。None という結果は、1 未満のサポートされていない値を表します。prime_factors(1) は、1 には素因数がないため [] を返します。

エラトステネスのふるいを使って素因数分解を行う

エラトステネスのふるいは、各素数の倍数を、その素数の二乗から順にマークすることで、上限までのすべての素数を見つけます。1 つの整数を因数分解するには、その整数までのふるいを構築し、リストされた各素数で可能な限り割り出します。このアプローチは、素数リストを再利用する場合に便利です。1 つの値を因数分解するためだけにふるいを構築すると、余分な作業が発生することがあります。以下のふるいは、その上限（その値を含む）までの素数を返します。これは、出力が表示されない構文とアルゴリズムの例です。

def primes_up_to(limit):
    if limit < 2:
        return []

    is_prime = [True] * (limit + 1)
    is_prime[0] = is_prime[1] = False
    candidate = 2
    while candidate * candidate <= limit:
        if is_prime[candidate]:
            for multiple in range(candidate * candidate, limit + 1, candidate):
                is_prime[multiple] = False
        candidate += 1
    return [number for number, prime in enumerate(is_prime) if prime]


def factor_with_sieve(number):
    if number < 1:
        return None
    factors = []
    for prime in primes_up_to(number):
        while number % prime == 0:
            factors.append(prime)
            number //= prime
    return factors

エラトステネスのふるいの詳細については、関連ガイドを参照してください。カスタム関数と同様に、このバージョンは 1 に対して [] を返し、1 未満の値に対して None を返します。

primefac モジュールを使って素因数分解を行う

primefac は外部の Python パッケージであるため、プログラムを実行する環境にインストールされている必要があります。その primefac() 関数は素因数を生成します。シーケンスとして表示または保存する必要がある場合は、結果をリストに変換してください（list(primefac.primefac(20))）。この選択肢では、因数分解ロジックはカスタム関数ではなくパッケージ側に置かれます。パッケージの呼び出しはインラインで示されています。これは、この記事の自己完結型の例にはその外部依存関係が含まれておらず、インストールもしないためです。