A : Prime Factorize

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

素因数分解

整数 n を素因数分解してください。

入力

n

1つの整数 n が1行に与えられます。

出力

入力値n:(コロン)の後に、素因数を昇順に並べて出力します。ただし、同じ素因数でnを複数回割れる場合は、その素因数は回数分出力します。各素因数の前に1つの空白を出力して下さい。

制約

  • 2 ≤ n ≤ 109

入力例 1

12

出力例 1

12: 2 2 3

入力例 2

126

出力例 2

126: 2 3 3 7