In thừa số kèm số mũ (Prime Factors with Exponents)

Nguồn: Phước Hưng OJ

Phiên bản: Phước Hưng OJ Extended

Đề bài

Cho số nguyên $n\ge2$. Phân tích $n$ thành tích các lũy thừa của số nguyên tố. Với mỗi số nguyên tố $p$ xuất hiện trong phân tích, gọi $e$ là số lần $p$ xuất hiện làm thừa số, tức $n$ chia hết cho $p^e$ nhưng không chia hết cho $p^{e+1}$. Hãy in mỗi cặp $p,e$ trên một dòng, các dòng theo thứ tự $p$ tăng dần. Mỗi số nguyên tố chỉ được in một lần.

Input

Một dòng chứa một số nguyên $n$.

Output

Mỗi dòng in hai số nguyên $p$ và $e$, cách nhau một dấu cách: thừa số nguyên tố và số mũ tương ứng, theo $p$ tăng dần.

Subtask

• Subtask 1 (20%): $2\le n\le10^4$.
• Subtask 2 (30%): $2\le n\le10^8$.
• Subtask 3 (50%): $2\le n\le10^{12}$.

Ví dụ

Ví dụ 1

Input:

360

Output:

2 3
3 2
5 1

Giải thích: Ta có $360=2\cdot2\cdot2\cdot3\cdot3\cdot5=2^3\cdot3^2\cdot5^1$. Vì $2<3<5$, chương trình in ba dòng 2 3, 3 2, 5 1.

Ví dụ 2

Input:

13

Output:

13 1

Giải thích: $13$ là số nguyên tố nên chỉ có một thừa số nguyên tố $13$ với số mũ $1$.

Ví dụ 3

Input:

64

Output:

2 6

Giải thích: Chia liên tiếp $64\to32\to16\to8\to4\to2\to1$ bởi $2$ đúng $6$ lần. Do đó $64=2^6$ và chỉ có một dòng 2 6.