小テスト(2) - 素因数分解

2以上の整数をひとつ入力して, その素因数を小さい方から順に 一行にひとつずつ出力するプログラムを作る. たとえば入力が 30 だったとすると, 出力はこうなる. 
2
3
5
同じ素因数を複数持つ場合, その回数だけ出力する. たとえば入力が 40 の場合には, 出力はこうなる. 
2
2
2
5
となる. また, 入力が素数だった場合, たとえば 29 の場合には, その数だけを出力する. 
29
(ヒント) 与えられた数を「小さな素数」から順に割っていけばよい. たとえば 40 だったら, まず 2 で割れるので 20, さらに 2 で割れるので 10, さらに 2 で割れるので 5. もう 2 では割れなくなったから, 次の素数である 3 でやってみると, 割れない. 次の素数の 5 でやってみると割り切れて結果は1. これで素因数分解は終了ということになる.

ただ, この方式では, 素数をあらかじめ準備しておかないといけない. そこで計算は遅くなるけれどそれを省くアイデアをひとつ. 「小さな素数」ではなく「小さな整数」で順に割っていっても 同じ結果が得られる. なぜなら, 合成数で割れることがあるなら, その合成数の素因数でその前に割れているはずだから.