Python で素因数分解する

【実習】自然数を入力して、素因数分解するプログラムを作ろう。

　さて、このプログラムではループを作ることになりますが、意外と難しい。
　1400 を素因数分解する場合を考えてみましょう。まず 2 で割れるかどうか調べて、この場合は 2 で割れるので、割ると$${1400=2\times700}$$ 。さて、問題はその次です。2 で割った後に 3 で割れるかどうか・・・ではありませんよ。もう一度、2 で割れるかどうか調べます。
　こうして 2 で割れる限りは割り続けて、2 で割り切れなかったら 3 で割れるかどうかを調べる。3 で割れる可能性も１回とは限りませんから、3 で割り切れる限りは割り続けて、割れなかったら 4 で・・・と続きます。
　ところで、ループの作り方には for と while の２種類があります。さて、この場合はどちらを使うべきかと言うと、for で回すのは現実的ではありませんね。理由の１つは、先ほども述べたように「ある数（例えば 2）で割り切れる回数が何回か分からない」からです。
　for で回すのが現実的でない理由がもう１つあります。1400 を素因数分解する場合、for 文で1400回転しても良いですが、この場合は実際には$${1400=2^3\times5^2\times7}$$ですから、２から７まで回せば十分なわけです。1400回転もするのは、いくら何でも無駄ですね（一方で、その数が素数かもしれないので、途中で止めるわけにもいかない。とは言え、√n までやれば十分でもある）。というわけで、このプログラムは「while 文でループ」を作るのが現実的でしょう。では、どうぞ。

---

　次のプログラムの４行目から９行目までがループの部分です。ループの中に if 文と else 文が入っていて、もし（if）「ある数ｉで割り切れたら、ｉの値を変えずに」再び割れるかどうかを調べ、そうでなかったら（else）「ｉの値を１つ増やして」割れるかどうかを調べます。

n=int(input("自然数を入力してください "))
print(n,end="=")
i=2
while i<n:
    if n%i==0:
        print(i,end="×")
        n=n//i
    else:
        i=i+1
print(n)

　実行してみました。

自然数を入力してください　5963
5963=67 *89

　5963（ご苦労さん）は合成数です。素因数分解すると、連番「6→7→8→9」が並びます。67 も 89 も素数です。

自然数を入力してください　1111111
1111111=239 *4649

　1,111,111 も合成数です。素因数分解すると、239 *4649 となる。「にっ（と笑って）サンキュー、よろしく」とでも読みましょうか？　239 も 4649 も素数です。

自然数を入力してください 108
108=2×2×3×3×3

　こんな数でも大丈夫。期待通りに表示してくれました。

自然数を入力してください　17
17=17

　素数を入力すると、上のようにその数だけを直に書いてくれます。
　意外と短いコードで書けました！　めでたしめでたし。

◇　　　　　　◇　　　　　　◇

〜 Python で２重ループ・３重ループ 〜
▷ Python が九九81匹　　　　　　　
▷ Python で素因数分解する　　　　
▷ Python でピタゴラス数を書き出す