素因数分解 (試し割り法) の根本理解 - Python3

競技プログラミングサイトで遊んでいると、素因数分解の知識が必要となり、再勉強をした。

１．素因数分解を思い出す。
小さい素数から、割り算を繰り返して、これ以上どの数字でも割れないとなったら終了という理解。(以下の画像のイメージ)

これを、試し割り法というとの事。

２．試し割り法のアルゴリズムの理解を深める。
以下のサイトを参考にさせて頂いて、試し割り法のアルゴリズムを見た。
Thanks!!
・Pythonで素因数分解する
・素数と仲良しになる3つのプログラム

が、素人の為、正直良くわからない部分があり、１行づつ理解を深めて見た。

私の理解としては。。。

ある数（素数候補）として、初期値を２とする。

①”ある数（素数候補）”で割り切れるかどうかを見る？
②入力数字を”ある数”で実際に割り、商に置き換える。

①と②を割りきれなくなるまで繰り返す。

割り切れなくなったら、
③次に、”ある数”を１つ大きくして、①と②を繰り返す。

で、④残りの数を、”ある数”で割った商が、”ある数”よりも小さくなったら終わり。
何故なら、２から初めて、１づつ”ある数”を大きくしながらで割っていくので、
これより先、割り切れる事はない。（割り切れるなら、この段階にくるまでに割り切れているはず。）

。。。。ということで、説明は上手くないが、以下を実行して、腹落ちした。



以下、上記プログラムの実行結果。３６０を素因数分解している。

-> % python factorization.py
３６０
360の素因数分解をする。

CP1: 2で割り切れるかどうか調べる。
CP2: 2で割り切れたから、2を出力する。
この時点の商：180
この時点の出力予定：[2]
まだ、2で割り切れるかどうかを確認する。

CP2: 2で割り切れたから、2を出力する。
この時点の商：90
この時点の出力予定：[2, 2]
まだ、2で割り切れるかどうかを確認する。

CP2: 2で割り切れたから、2を出力する。
この時点の商：45
この時点の出力予定：[2, 2, 2]
まだ、2で割り切れるかどうかを確認する。

CP3: 2では、もう割り切れなくなったので、
次は、3で割り切れるかどうかを試す。

CP1: 3で割り切れるかどうか調べる。
CP2: 3で割り切れたから、3を出力する。
この時点の商：15
この時点の出力予定：[2, 2, 2, 3]
まだ、3で割り切れるかどうかを確認する。

CP2: 3で割り切れたから、3を出力する。
この時点の商：5
この時点の出力予定：[2, 2, 2, 3, 3]
まだ、3で割り切れるかどうかを確認する。

CP3: 3では、もう割り切れなくなったので、
次は、4で割り切れるかどうかを試す。

CP4: 5を4で、割ったとしても、商は4より小さくなるので、これ以上は検討不要。
残っている数を、最後の約数として追加する。ただし、１の場合は、無視する。
5を出力して計算終了。

output----
[2, 2, 2, 3, 3, 5]