Monday-Saturday Prime Factors

時間制限 : 3 sec, メモリ制限 : 65536 KB
英語版はこちら

Problem B: 月曜土曜素因数

審判長日誌,宇宙暦 48642.5. われわれは,初等整数論から出題することに決めた. 正整数の素因数をすべて求めることに似た問題だが, そうではない.

7 で割った余りが 1 または 6 である正整数は 7N+{1,6} 数と呼ばれる. しかし,発音しにくいので, 月曜土曜数と呼ぼう.

月曜土曜数 a, b に対して, 月曜土曜数 x が存在して ax = b が成り立つとき, ab月曜土曜約数と呼ぶ. 月曜土曜数 a が月曜土曜数 b の月曜土曜約数であるためには, ab の普通の意味の約数であれば必要十分であると, 簡単に証明できる.

1 より大きな月曜土曜数でそれ自身と 1 の他に月曜土曜約数をもたないものを, 月曜土曜素数と呼ぶ. 普通の意味の素数である月曜土曜数は月曜土曜素数であるが, 逆は一般に成り立たない. たとえば,27 は普通の意味の素数ではないが,月曜土曜素数である. 月曜土曜数 a の月曜土曜約数である月曜土曜素数を, a月曜土曜素因数と呼ぶ. たとえば, 27 は月曜土曜素数であり, 216 = 27 × 8 が成り立つので, 27 は 216 の月曜土曜素因数のひとつである.

1 より大きなどんな月曜土曜数も, 1 個以上の月曜土曜素数の積として表すことができる. 表し方は,順序の違いを無視しても,必ずしも一通りではない. たとえば, 216 = 6 × 6 × 6 = 8 × 27 である.

選手は, 入力された各々の月曜土曜数に対して, その月曜土曜素因数をすべて出力するプログラムを書かなくてはならない.

Input

入力は行の並びで,各行に一つの月曜土曜数が含まれている. 各々の月曜土曜数は 1 より大きく 300000 (三十万)より小さい. 入力の終わりは,数字 1 が 1 文字だけ含まれる行で示される.

Output

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

Sample Input

205920
262144
262200
279936
299998
1

Output for the Sample Input

205920: 6 8 13 15 20 22 55 99
262144: 8
262200: 6 8 15 20 50 57 69 76 92 190 230 475 575 874 2185
279936: 6 8 27
299998: 299998

Source: ACM International Collegiate Programming Contest , Japan Domestic Contest, Aizu, Japan, 2008-07-04
http://sparth.u-aizu.ac.jp/icpc2008/