はじめに
とある友人から、これまたとあるプログラムの作成を依頼されたときに即席で素因数分解のコードを組んだのですが、再帰処理を使えば意外と短く素因数分解のコードを書くことができたので紹介します。
コード
stack = []
def prime_factorization(target):
# type:(int)->None
for i in range(2, target):
if target % i == 0:
stack.append(i)
next_mod = target // i
prime_factorization(next_mod)
return
stack.append(target)
prime_factorization(2**10) #結果->[2, 2, 2, 2, 2, 2, 2, 2, 2, 2]
気持ち程度の解説
まずやることは、調べたい数字が割り切れるかどうかです。ここではfor文で１と自分の数字以外でわれるかどうかという脳筋手法で調べています。
そして、素数の場合はリストに追加し、逆に割り切れる場合は、調べたい数字を割った上で再帰します。
終わりに
「Python 素因数分解」と調べると素因数分解をしてくれる関数があるライブラリが出てきますが、そういうライブラリが使えないというような状況になった場合にぜひ参考にしてください。
8/24追記
私の書いた再帰処理は、コードが短くなる一方でメモリがかなり食われてしまったり、グローバル変数を使わなければならないといった欠点があります。
そういった欠点を抑えつつ、簡潔なプログラムをコメントで教えていただいたので、追記させていただきます。
def prime_factorization(value: int) -> list:
primes = []
for i in range(2, value):
while value % i == 0:
primes.append(i)
value //= i
if value == 1:
break
return primes
print(prime_factorization(2**10)) #結果->[2, 2, 2, 2, 2, 2, 2, 2, 2, 2]
print(prime_factorization(12345678)) #結果->[2, 3, 3, 47, 14593]
def prime_factorization(value: int) -> generator:
i = 2
while i <= value:
while value % i == 0:
yield i
value //= i
i += 1
print(list(prime_factorization(2**10))) #結果->[2, 2, 2, 2, 2, 2, 2, 2, 2, 2]
print(list(prime_factorization(12345678))) #結果->[2, 3, 3, 47, 14593]
特に２つ目はPythonのgeneratorを利用したかなりイケてるコードですねしゅごい...