Skip to content

素因数分解

整数 \(N\) を素数の積に分解するアルゴリズム。

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

\(2 \sim N\) の各数で割り切れるだけ割っていくことで素因数分解できる。
計算量は \(O(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

if __name__ == "__main__":
    print(prime_factorization(24))   # {2: 3, 3: 1}
    print(prime_factorization(31))   # {31: 1}
    print(prime_factorization(1978)) # {2: 1, 23: 1, 43: 1}

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

\(N\) の素因数のうち \(\sqrt{N}\) より大きいものは高々1つしかない。

証明：

  • \(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

if __name__ == "__main__":
    print(prime_factorization(24))   # {2: 3, 3: 1}
    print(prime_factorization(31))   # {31: 1}
    print(prime_factorization(1978)) # {2: 1, 23: 1, 43: 1}

関連

参考