素人が素因数分解のアルゴリズムを作ってみた
タイトル通りです。知識をそこまで持たない私が何かしらアルゴリズムを作ろうとし、対象にしたのが素因数分解でした。
このアルゴリズムを作るにあたって私は、訓練のためなるべく情報を収集しないというルールを課しています。つまり、この記事のアルゴリズムは最適化や効率よりも理解しやすさに重きを置いているわけです。
そういうわけなので、実用性のある素因数分解のアルゴリズムを探している方はwikipediaや他の記事を参考にすることをおすすめします。あくまでこの記事は初心者でもフローが理解できる素因数分解のアルゴリズムを紹介するといった趣旨です。
また、アルゴリズムを作ることが目標だったので、特にこれを改良するというつもりもありません。動かない場合はアレですが、そうでない指摘はご容赦を。
さっそくコードを載せる
import math
def calcPrime(n:int) -> [int]:
p=[1 for i in range(n+1)]
p[0],p[1]=0,0
k=2
while k<=n:
if p[k]==1:
q=k*2
while q<=n:
p[q]=0
q+=k
k+=1
return p
def disaN(n:int) -> [int]:
p=calcPrime(n)
m=int(math.log(n)/math.log(2))
q=[0 for i in range(m)]
i=2
n0=n
while i<=n0:
if p[i]==1 and n%i==0:
for j in range(m):
if q[j]==0:
q[j]=i
break
n//=i
if n%i!=0:i+=1
if q[-1]!=0:break
else:i+=1
q=[i for i in q if i!=0]
return q
結果
if __name__=="__main__":
print(disaN(77777))
[7, 41, 271]
五桁くらいなら結構早いです。
収集"してしまった"情報
私はなるべく情報を集めないようにしていましたが、ある問題を解決するために一つだけ調べてしまったことがありました。それは「ある整数の持つ素因数の個数をおさえられる値」です。一応この情報がなくともappendメソッドを使えば実装ができたのですが、appendメソッドの処理は重いのでなるべく使いたくありませんでした。appendを使った場合であれば情報収集なしでも実装でき、それでも動くはずなのでノーカン……にはなりませんよね……。
アルゴリズムの解説
まず、calcPrimeという関数の中にはエラトステネスのふるい方式で素数を求めるというアルゴリズムが定義されています。これはnを引数として渡すとnまでの素数を全部見つけ、n+1の長さのリストを作り、インデックスが素数になっている要素を1に、インデックスが素数でない要素を0にして出力する関数です。
ちなみに、エラトステネスのふるい式素数探索は昔に手法を覚えていたので調べずに実装できました。
次に、disaNという関数も引数nを取りますが、これは素因数分解したい数のことです。disaNでは最初にcalcPrimeを呼び出し、素因数分解するための素数を集めます。
素数が集まったら2(一番最初の素因数)からn(素因数分解したい数)までの素数に対してループ処理がされます。ここで行われる処理はいわゆる試し割り法的なもので、nが割り切れる素数を見つけたらnをその素数で整数除算し、素数をリストに保存。nは割られたまま次のループへ進みます。ただし2^2=4のように同じ素因数を持つ数があるため、次も同じ素数で割り切れそうだったら素数を変えずにブロック先頭へ戻らなければなりません。この処理が必要なためにforではなくwhileを使いました。
最終的に、その数がもてる素因数の個数の限界まで素因数が見つかるか、最後の素数の判定が終わるとループを抜け、その時点で見つかった素因数をリスト化したものが返されます。
応用
このアルゴリズムを利用することで、最大公約数や最小公倍数を求めるアルゴリズムも作ることができます。方法は二つの整数に対して素因数分解をし、その結果得られる二つのリストの共通部分と和集合をとる、というものです。ただ、正直この方法はめちゃくちゃ非効率です。真っ先に試した私が言うのも何ですが、このやり方はやらない方がいいでしょう。