Phân tích ra thừa số nguyên tố (Prime Factorization)

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

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

Đề bài

Cho n≥2. Phân tích n thành tích các thừa số nguyên tố và in từng thừa số theo thứ tự không giảm, có lặp lại theo số mũ. Ví dụ 72 = 2×2×2×3×3 nên in 2 2 2 3 3. Đầu ra chỉ chứa các số, ngăn cách một dấu cách, không in ký hiệu nhân.

Input

Một số nguyên n.

Output

Một dòng chứa dãy thừa số nguyên tố theo thứ tự không giảm, ngăn cách bằng một dấu cách, không có dấu cách cuối.

Subtask

• Subtask 1 (20%): 2 ≤ n ≤ 1000.

• Subtask 2 (30%): 2 ≤ n ≤ 10^8.

• Subtask 3 (50%): 2 ≤ n ≤ 10^12.

Ví dụ

Ví dụ 1

Input:

72

Output:

2 2 2 3 3

Giải thích: 72 chia lần lượt cho 2 ba lần rồi cho 3 hai lần.

Ví dụ 2

Input:

97

Output:

97

Giải thích: 97 là số nguyên tố.

Ví dụ 3

Input:

2

Output:

2

Giải thích: Số nguyên tố nhỏ nhất.