2017年度「アルゴリズムとデータ構造」のページ

課題(別紙)

如月素因数

正の偶数を如月数と呼ぶことにする。如月数\(a\), \(b\)に対して、如月数\(x\)が存在して \(ax = b\) が成り立つとき、\(a\)を\(b\)の如月約数と呼ぶ。如月約数をもたない如月数を如月素数と呼ぶ。

如月数を如月素数の積の形で表したものを、 如月素因数分解と呼ぶ。 順序の違いは無視する。 たとえば、\(6\times50\) と \(50\times6\) は同一視する。

どんな如月数にも一通り以上の如月素因数分解があるが、一意性は必ずしも成り立たない。 たとえば、 \(300 = 2 \times 150 = 6 \times 50 = 10 \times 30\) である。

如月素因数分解の各々の如月素数を如月素因数と呼ぶ。 たとえば、\(6\times50\) は\(300\)の如月素因数分解なので、\(6\)は\(300\)の如月素因数である。\(a\)と\(b\)がいずれも\(c\)の如月素因数でも、積 \(ab\) が \(c\) の如月約数とは限らない。たとえば、\(6\)も\(30\)も\(300\)の如月素因数だが、\(6\times30\) は\(300\)の如月約数ではない。

あなたの任務は、入力された各々の如月数に対して、その如月素因数をすべて出力するプログラムを書くことである。

入力

入力は行の並びで、各行に一つの如月数が含まれている。各々の如月数は\(300000\)(三十万)より小さい。

出力

入力された如月数それぞれに対して、その数が表示され、つづけて同じ行に、コロン「:」、そして、如月素因数の並びが、それぞれの前に空白を置いて小さい順に出力されなくてはならない。各如月素因数は、たとえ入力された如月数を2回以上割るものであっても、ちょうど1回だけ出力されなくてはならない。