MATH - Tích các thừa số nguyên tố

Đề bài

Cho số nguyên dương \(N\). Hãy phân tích \(N\) thành tích các lũy thừa của các số nguyên tố.

Dữ liệu vào

Một dòng duy nhất chứa số nguyên dương \(N\).

Dữ liệu ra

Với mỗi thừa số nguyên tố của \(N\), in ra một dòng gồm hai số nguyên:

• Thừa số nguyên tố.
• Số mũ của thừa số nguyên tố đó trong phân tích.

Hai số trên cùng một dòng được ngăn cách bởi một dấu cách. Các thừa số nguyên tố phải được in theo thứ tự tăng dần.

Ràng buộc

• \(2 \le N \le 10^9\).

Subtask

• Subtask 1 (30%): \(2 \le N \le 10^6\).
• Subtask 2 (70%): Không có ràng buộc bổ sung.

Sample Input 1

4

Sample Output 1

2 2

Sample Input 2

168

Sample Output 2

2 3
3 1
7 1

Giải thích

Với mẫu thứ nhất:

Ta có \(4 = 2^2\), vì vậy chỉ có một thừa số nguyên tố là \(2\) với số mũ bằng \(2\).

Với mẫu thứ hai:

Ta có \(168 = 2^3 \times 3^1 \times 7^1\), nên kết quả lần lượt là:

• \(2\) có số mũ \(3\).
• \(3\) có số mũ \(1\).
• \(7\) có số mũ \(1\).