Trong lý thuyết số học, số nguyên tố đóng vai trò nền tảng cho nhiều hệ thống mã hóa và bảo mật. Giáo sư Toán học yêu cầu bạn liệt kê tất cả các số nguyên tố không vượt quá một ngưỡng \(N\) cho trước. Hãy viết chương trình sử dụng phương pháp sàng số nguyên tố để thực hiện yêu cầu này một cách hiệu quả nhất.

Định dạng đầu vào

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

Định dạng đầu ra

• In ra tất cả các số nguyên tố nhỏ hơn hoặc bằng \(N\) theo thứ tự tăng dần, cách nhau bởi một dấu cách.

Ví dụ

Input:

10

Output:

2 3 5 7

Ràng buộc

• 30% số điểm ứng với \(N \le 1000\).
• 70% số điểm còn lại không có ràng buộc gì thêm.