python初心者が素因数分解機を作る

今回はpythonで素因数分解をしてくれるコードを書いてみました。

全体はこんな感じ。

from math import floor

#素因数分解する数を入力
fact_num = int(input('素因数分解する数を入力'))

#割り続ける処理
def divide(dividend, divisor):
    global list_fact
    while True:
        quotient1 = dividend / divisor
        quotient2 = floor(quotient1)
        if quotient1 == quotient2:
            list_fact.append(divisor)
            dividend = dividend / divisor
        else:
            return(dividend)

#素因数分解する数が1の場合はリストに1を入れる
if fact_num == 1:
    list_fact = [1]
else:
    list_fact = []

#2の倍数ならば2で割り続ける
fact_num = divide(fact_num, 2)

#3の倍数ならば3で割り続ける
fact_num = divide(fact_num, 3)

x = 1

#4以降の素数で割り続ける(6の倍数±１の数で割り続ける)
while fact_num != 1:
    fact_num = divide(fact_num, 6 * x - 1)
    fact_num = divide(fact_num, 6 * x + 1)
    x += 1

print(list_fact)

現在絶賛プログラミング勉強中ですが、こんなものを作れるようになると成長を実感できますね。いや満足してはいけません。精進して参ります。ちなみに私と同じく勉強中って人は参考にしないほうがいいと思います。じゃあ何の為にブログに載せてるのかね。

仕組みとしては、input関数で素因数分解したい値を入力し、素数で割り続けていき、素因数をリストに入れていくというのが大まかな流れです。

実際には素数で割り続けている訳ではなく、2と3で割り続けた後に6の倍数±1の値で割り続けています。実は2と3を除いて素数は6の倍数の前後にしかありません。知らなかったって人は調べてみてね。

ただし6の倍数の前後の数が全て素数であるというわけではないので（例えば25）、このプログラムでは25などの素数でない値（合成数）でも割っていることになります。しかし、このプログラムでは「割られる数に割る数が含まれている時、割る数（素因数）をリストに入れる」という処理をしており、また2で割ったあと3で割る、5で割る、7で割る...といった風に小さい数から順に割っています。つまり、25などの合成数で割ったとしても、割られる数には含まれていない為その数がリストに含まれることはありません。（たぶん）

そして素因数分解した結果をリストとして表示しています。

どうですかねコレ。自分自身全くの初心者ですのでこれが良いコードなのかどうかもさっぱり分かりません。なんか出来ちゃった〜って感じ。有識者の方ぜひともご教授願います。

そして余談なんですけど、コレ作った後に知ったんですが、Sympyとかいう便利なパッケージがあるらしい。prime(n)でn番目の素数を返してくれます。なんやそれ。こんな6の倍数がどうたらこうたらせんで良かったやん。

ということでまた一つ賢くなれました。