きっかけ

前回、素数を求めるプログラムを書いている時に、素因数分解を解きたくなったからです。

動作環境

Windows10 Pro
Python3.6.2

素因数分解する

試し割り法を用いて素因数分解したいと思います。
試し割り法 - Wikipedia
簡単に処理の流れを説明

素因数分解したい数字をNとする
①2から√Nまでの数字を一つずつ取り出す
②Nを取り出した数字(以下numとする)で割り切れなくなるまで割る
③割り切れたら素因数リストにnumを追加していく
④割り切れなくなったら次の数字を取り出す

trial_division.py

import math
# 試し割法
def trial_division(n):
    #素因数を格納するリスト
    factor = []
    #2から√n以下の数字で割っていく
    tmp = int(math.sqrt(n)) + 1
    for num in range(2,tmp):
        while n % num == 0:
            n //= num
            factor.append(num)
    #リストが空ならそれは素数
    if not factor:
        return 'prime number'
    else:
        factor.append(n)
        return factor

def main():
    number = int(input("素因数分解したい数字を入力してください:"))
    print(trial_division(number))

if __name__ == "__main__":
    main()

実行結果

PS C:\Python\math> python .\trial_division.py
素因数分解したい数字を入力してください:100
[2, 2, 5, 5, 1]

行けてますね

今回はこれで終わりたいと思います。
ありがとうございました。