pythonで素因数分解

素因数分解に使った数をlistで返す。

80の素因数分解で試作

n = 80
lis=[]

for i in range(2,n+1):
    while True:
        if n%i == 0:
            lis.append(i) # 余り0なら素因数分解リストにappendする
            n = n//i # nの更新
            print(lis)
            print("n={}".format(n)) # nの更新状況をみてみる
        else:
            break

考え方は中学生と同じ
$n = 80$ でスタート
〜2の素因数分解にTry する〜
$80÷2=40$
余り:0→素因数分解リストに2をappend
$n = 40$ に更新

$40÷2=20$
余り:0→素因数分解リストに2をappend
$n = 20$ に更新

$20÷2=10$
余り:0→素因数分解リストに2をappend
$n = 10$ に更新

$10÷2=5$
余り:0→素因数分解リストに2をappend
$n = 5$に更新

$5÷2=2$
余り:1→appendせず
$n$ 更新せず
〜2の素因数分解は終了〜

〜3の素因数分解にTryする〜
$n = 5$ から再開
$5÷3=1$
余り:2→appendせず
$n$ 更新せず
〜3の素因数分解は終了〜

〜4の素因数分解にTryする〜
$n = 5$ から再開
$5÷4=1$
余り:1→appendせず
$n$ 更新せず
〜4の素因数分解は終了〜

〜5の素因数分解にTryする〜
$n = 5$ から再開
$5÷5=1$
余り:0→素因数分解リストに5をappend
$n = 1 $に更新
〜5の素因数分解は終了〜


6以降進んでいっても、素因数分解リストが更新されることはない。
なぜなら、更新された $n= 1$ を割り切れるものは以降に存在しないため。
ただ、以降の繰り返しを大きな数で実行すると時間がかかりすぎるので、rangeのゴールは調整する必要がある。

素因数分解は平方根より以下の全ての素数を確認で十分という性質を中途半端に使う。
割り算をTryさせる数を2から、調べたい数の平方根以下までに設定する。

nがnの平方根より大きなポイントでbreakしていたらそれをリストにappend
素数の時もこの挙動になる
この処理を最後に加筆

以上を踏まえて関数にする。

def prime_factorization(n):
    """
    task:prime factorization
    return:prime
    type:list
    """
    lis=[]
    for i in range(2,int(n**0.5)+1): # 割り算のTryは2から、平方根以下まで
        while True:
            if n%i == 0:
                lis.append(i) # 余り0なら素因数分解リストにappendする
                n = n//i # nの更新
                
            else:
                break
                
    if n > int(n**0.5): # nが　int(n**0.5) より大きなポイントでbreakしていたらそれをリストにappend 素数の時もこれ
        lis.append(n)

    return lis

n = int(input("nは?>"))
print(prime_factorization(n))

注）絞り込みについて

for i in range(2,int(n**0.5)+1)

rangeの絞り込みが緩い（4とか6とか素数でない数でも割り算のTryをしている）ので、処理時間を考えると有能ではないと思われる。
とりあえず課題はクリアできる。
13606292703345なので10兆までは対応していた。
どこかで限界を迎えるはず。