1397 - 山本式素因数分解

問題

偉大で聡明で博識で天才で$\ldots$な数学者ドンキー山本は、以下の遊びをすることにした。

• $1$ から $N$ までのすべての自然数の積を素因数分解する。

助手のあなたは、ドンキー山本の計算が合っているかどうかを調べるため、コンピューターで上の操作を行うことになった。

入力

入力は以下の形式で標準入力から与えられる。

$N$

1行目に整数 $N$ が与えられる。

出力

素因数分解で求まった数を以下の形式で出力する。

$a_1$ $b_1$
$a_2$ $b_2$
$\vdots$

• $a_i$ は素因数分解で得られた自然数、$b_i$ は $a_i$ の個数である。
• $a_i$ は昇順ソートをすること。
• 出力の最後に改行を入れること。

制約

全ての入出力ケースについて以下を満たす。

• $2 \leq N \leq 10^{6}$

入出力例

入力例1

3

出力例1

2 1
3 1

$1 \times 2 \times 3 = 6$であり、素因数分解すると $2$ が $1$ 個、$3$ が $1$ 個となる。

入力例2

4

出力例2

2 3
3 1

解説（クリックで開く）

まず、すべての数を掛けるとN!となり、非常に大きな値になってしまいます。そこで、「2~Nまでの数をそれぞれ素因数分解する」という考えになります。一つずつ素因数分解していくとTLEになるため、エラトステネスの篩を使った高速な素因数分解を使用します。その名の通り高速で素因数分解した値を求めることができ、正解となります。