Pythonで素因数分解を実装する方法【試し割り法を徹底解説】
素因数分解は、自然数を素数の積で表現する重要な数学的操作です。Pythonでの効率的な実装方法から高速化技法まで、実用的なコード例とともに詳しく解説します。
素因数分解とは
素因数分解とは、自然数nを素数の積として表現することです。例えば：
- 12 = 2² × 3
- 60 = 2² × 3 × 5
この記事では最も基本的な「試し割り法」を中心に実装方法を説明します。
基本的な素因数分解実装
最もシンプルな試し割り法の実装：
def prime_factors(n):
factors = []
d = 2
while d * d <= n:
while n % d == 0:
factors.append(d)
n //= d
d += 1
if n > 1:
factors.append(n)
return factors
# 使用例
print(prime_factors(60)) # [2, 2, 3, 5]
print(prime_factors(17)) # [17]
print(prime_factors(100)) # [2, 2, 5, 5]
辞書形式での素因数分解
指数も含めて返す実装：
def prime_factors_dict(n):
factors = {}
d = 2
while d * d <= n:
while n % d == 0:
factors[d] = factors.get(d, 0) + 1
n //= d
d += 1
if n > 1:
factors[n] = 1
return factors
# 使用例
print(prime_factors_dict(60)) # {2: 2, 3: 1, 5: 1}
print(prime_factors_dict(144)) # {2: 4, 3: 2}
高速化された実装
2と奇数のみをチェックする最適化版：
def fast_prime_factors(n):
factors = []
# 2で割り切れる間は2を追加
while n % 2 == 0:
factors.append(2)
n //= 2
# 3以上の奇数で試し割り
d = 3
while d * d <= n:
while n % d == 0:
factors.append(d)
n //= d
d += 2
if n > 1:
factors.append(n)
return factors
# 使用例
print(fast_prime_factors(315)) # [3, 3, 5, 7]
より効率的な実装（mathモジュール使用）
import math
def optimized_prime_factors(n):
factors = []
# 2の処理
while n % 2 == 0:
factors.append(2)
n //= 2
# 奇数のみチェック
for i in range(3, int(math.sqrt(n)) + 1, 2):
while n % i == 0:
factors.append(i)
n //= i
if n > 2:
factors.append(n)
return factors
実用的な活用例
最大公約数（GCD）の計算
def gcd_by_factors(a, b):
factors_a = prime_factors_dict(a)
factors_b = prime_factors_dict(b)
gcd = 1
for prime in factors_a:
if prime in factors_b:
gcd *= prime ** min(factors_a[prime], factors_b[prime])
return gcd
print(gcd_by_factors(48, 18)) # 6
完全数の判定
def is_perfect_number(n):
factors = prime_factors_dict(n)
divisor_sum = 1
for prime, count in factors.items():
divisor_sum *= (prime ** (count + 1) - 1) // (prime - 1)
return divisor_sum - n == n
print(is_perfect_number(28)) # True
複数の数の素因数分解
def batch_prime_factors(numbers):
return {num: prime_factors(num) for num in numbers}
numbers = [12, 15, 18, 20]
result = batch_prime_factors(numbers)
for num, factors in result.items():
print(f"{num}: {factors}")
パフォーマンス比較
大きな数での処理時間を測定：
import time
def time_factorization(func, n):
start = time.time()
result = func(n)
end = time.time()
return result, end - start
# 比較例
n = 1000003 # 大きな素数
basic_result, basic_time = time_factorization(prime_factors, n)
fast_result, fast_time = time_factorization(fast_prime_factors, n)
print(f"基本実装: {basic_time:.4f}秒")
print(f"高速実装: {fast_time:.4f}秒")
まとめ
素因数分解は数論の基礎となる重要なアルゴリズムです。試し割り法の基本実装から最適化技法まで理解することで、暗号化アルゴリズムや数学的計算での応用が可能になります。
大きな数を扱う場合は、より高度なアルゴリズム（ポラード・ロー法など）の検討も必要ですが、多くの実用場面では今回紹介した手法で十分対応できます。
■プロンプトだけでオリジナルアプリを開発・公開してみた！！
■AI時代の第一歩！「AI駆動開発コース」はじめました！
テックジム東京本校で先行開始。
■テックジム東京本校
「武田塾」のプログラミング版といえば「テックジム」。
講義動画なし、教科書なし。「進捗管理とコーチング」で効率学習。
より早く、より安く、しかも対面型のプログラミングスクールです。
＜短期講習＞5日で5万円の「Pythonミニキャンプ」開催中。
＜月1開催＞放送作家による映像ディレクター養成講座
＜オンライン無料＞ゼロから始めるPython爆速講座
