試し割り法による素因数分解

概要

素因数（prime factor）とは、ある自然数の約数となる素数のことです。また素因数分解 (prime factorization) とは、自然数を素因数の積の形で表すことを指します。例えば360を素因数分解すると、$2^3$ × $3^2$ × $5^1$と表すことができます。本記事では2以上の自然数の素因数を試し割り法で列挙する手法を紹介します。

方針

基本的な考え方としては、与えられた2以上の自然数nに対して、nより小さい数で割り切れるかどうかを順番に確かめることで素因数判定を行っていきます。nを割り切る素因数を見つけた際、その素因数の累乗でも割り切れるかどうかも同時に確認しておくと効率的です。素因数候補として確かめるべき値の範囲は、2以上$\sqrt{n}$以下で十分です。

実装例

# Return a list of the prime factors for a natural number bigger than 1
def trial_division(n):
    if n < 2:
        return []

    prime_factors = []

    for i in range(2, int(n**0.5)+1):
        # nがi（の累乗）で割り切れるかを調べる
        while n % i == 0:
            # nがiで割り切れる場合、iを素因数としてリストに追加する
            prime_factors.append(i)
            # nをiで割った商で更新しておく
            n //= i
    # nの平方根より大きい素因数が存在する場合
    if n > 1:
        prime_factors.append(n)

    return prime_factors

n = int(input())
print(trial_division(n))

実行結果

# 入力
12
# 出力
[2, 2, 3]

# 入力
100
# 出力
[2, 2, 5, 5]

# 入力
600851475143
# 出力
[71, 839, 1471, 6857]

参考

試し割り法(Wikipedia)
Pythonで素因数分解（試し割り法）
Pythonで競技プログラミング〜基本的なアルゴリズム〜
[Python]試し割法で素因数分解する