素因数分解のアルゴリズム

アルゴリズム

\(2\sim N\)で割っていく

\(2\sim N\)の各数で割り切れるだけ割っていくことで素因数分解することができる。
この時の計算量は\(O(N)\)
そのため\(N\)が大きい場合は実行時間が大きくなる。

\(2\sim N\)の中には素数でない数(合成数)も存在する可能性があるが、その合成数を構成する素数はそれ以前に割りつくされているため、非素数が素因数分解の結果に混ざる心配はない。

from collections import defaultdict

# 計算量O(N)
def prime_factorization(n: int):  
    result = defaultdict(int)
    for i in range(2, n+1):
        # 割り切れるだけ割る
        while n % i == 0:
            n //= i
            result[i] += 1
    return result

def print_result(n, result):
    s = f"{n} = "
    for i, (j, k) in enumerate(result.items()):
        if i != 0:
            s += " + "
        s += f"{j}^{k}"

    print(s)

if __name__ == "__main__":
    print_result(24, prime_factorization(24))
    print_result(31, prime_factorization(31))
    print_result(1978, prime_factorization(1978))
24 = 2^3 + 3^1
31 = 31^1
1978 = 2^1 + 23^1 + 43^1

\(2\sim \sqrt N\)で割っていく

まず下記から\(N\)の素因数の内、\(\sqrt N\)より大きいものは高々一つしかないことがわかる。

  • \(N\)が\(p, q > \sqrt N\) かつ \(p \neq q\) となる約数\(p, q\)を持つと仮定する。
  • この時 \(pq > N\)となるが、\(p, q\)は\(N\)の素因数なので \(pq \leq N\)となることと矛盾する。
  • したがって \(p, q \leq \sqrt N\) (\(\sqrt N\)以下の素因数のみ) または \(p = q\) (\(\sqrt N\) より大きい素因数は1つのみ) となる。

つまり\(2\sim \sqrt N\)で割っていけば、最後に残る商が1か\(\sqrt N\)より大きい素因数となる。
この時の計算量は\(O(\sqrt N)\)

from collections import defaultdict
import math

# 計算量O(√N)
def prime_factorization(n: int):  
    result = defaultdict(int)
    for i in range(2, math.ceil(math.sqrt(n)) + 1):
        # 割り切れるだけ割る
        while n % i == 0:
            n //= i
            result[i] += 1

        if n == 1:
            break
    
    # 最後に残った商が1より大きければ、これが√Nより大きい唯一の素因数になる
    if n > 1:
        result[n] = 1
    
    return result

def print_result(n, result):
    s = f"{n} = "
    for i, (j, k) in enumerate(result.items()):
        if i != 0:
            s += " + "
        s += f"{j}^{k}"

    print(s)

if __name__ == "__main__":
    print_result(24, prime_factorization(24))
    print_result(31, prime_factorization(31))
    print_result(1978, prime_factorization(1978))
24 = 2^3 + 3^1
31 = 31^1
1978 = 2^1 + 23^1 + 43^1

コメント

タイトルとURLをコピーしました