Python で素因数分解する

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

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

---

　次のプログラムの４行目から８行目までが２重ループの部分です。

n=int(input('自然数を入力してください　'))
i=2
print(n,'=',end=(''))
while i<n:
    while n%i==0:
        print(i,'*',end=(''))
        n=n/i
    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 も素数です。

自然数を入力してください　2023
2023 =7 *17 *17 *1

　上のプログラム、小さい順に約数を書きますが、最後に同じ数が続く場合、見ての通り、最後に「*1」と書いてしまいます。無い方が良いのでしょうけれど、素因数分解できているし、意味もわかるので、これで良しとしましょう。

　と言いながら、一応作ってみました。上のコードに８行目と９行目を加えました。break はループから抜けるための命令で、ここでは内側の小ループから抜け出して、外側の大ループを続けるように組みました。もうちょっとシンプルに書きたいところですが、今のところこれで精一杯です。

n=int(input('自然数を入力してください　'))
i=2
print(n,'=',end=(''))
while  i<n:
    while n%i==0:
        print(i,'*',end=(''))
        n=n/i
        if n==i:                # 追加
            break               # 追加
    i=i+1
print(int(n))

◇　　　　　　◇　　　　　　◇

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