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

概要

素因数（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]

約数の列挙

約数はある整数を割り切ることのできる整数です。整数Nの約数とは、整数Nの素因数またはそれらを掛け合わせたものになるため、上記の素因数分解を利用して、整数Nの約数を列挙することもできます。
※この方法以外にも、単に1以上√N以下の整数で割り切れるか調べることで約数を列挙することもできます

実装例

import itertools

# nの約数のSetを返す
def get_divisors(n):
    # nの素因数のリストを得る
    prime_factors = trial_division(n)
    divisors = set()

    for i in range(1, len(prime_factors)+1):
        # 素因数をi個選んだ時の組み合わせ
        combinations = list(itertools.combinations(prime_factors, i))

        # 素因数を掛け合わせて約数を得る
        for comb in combinations:
            divisor = 1
            for num in comb:
                divisor *= num
            divisors.add(divisor)

    # 1を約数として加える
    divisors.add(1)
    return divisors

参考

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