Phân tích thừa số nguyên tố

Bối cảnh

Một số nguyên dương có thể được viết thành tích các số nguyên tố. Ví dụ 60 = 2 × 2 × 3 × 5.

Nhiệm vụ là in các thừa số nguyên tố theo thứ tự không giảm. Không cần lưu chúng vào mảng; có thể in ngay khi tìm được.

Yêu cầu

1. Đọc số nguyên n > 1.
2. Duyệt các ứng viên p từ 2 trở lên.
3. Trong khi n chia hết cho p, in p và chia n cho p.
4. Sau vòng lặp, nếu n còn lớn hơn 1 thì in phần còn lại.

Yêu cầu tổ chức code

Đóng gói phần xử lý trong một hàm printFactors(n) hoặc hàm tương đương.

Lưu ý: Online Judge chủ yếu kiểm tra tính đúng của output. Yêu cầu tổ chức code được dùng để rèn đúng kỹ năng của buổi học và sẽ được giảng viên quan sát khi chữa bài.

Input

Một số nguyên n.

Output

Các thừa số nguyên tố cách nhau một dấu cách, không có dấu cách thừa cuối dòng.

Ràng buộc

2 ≤ n ≤ 10^12.

Ví dụ 1

Input

60

Output

2 2 3 5

Giải thích

60 = 2 × 2 × 3 × 5, vì vậy các thừa số được in là 2 2 3 5.

Ví dụ 2

Input

2

Output

2

Giải thích

2 đã là số nguyên tố nên phân tích chỉ gồm chính số 2.

Thông tin học tập

• Module: M02
• Buổi: B07
• Loại bài: HOMEWORK
• Độ khó: Medium
• Concepts: functions, prime factorization, repeated division
• Giới hạn kiến thức: B01-B07
• Time limit: 2 second(s)
• Memory limit: 256 MB
• Point: 100