D. ERATOSTH - Sàng nguyên tố

Bộ nhớ: 256 MiB Thời gian: 100 ms Nhập/xuất từ luồng chuẩn
Kiểu bài: Thông thường Kiểu chấm: So sánh văn bản

Đề bài

Một số nguyên dương n > 1 được gọi là số nguyên tố nếu nó không có ước nguyên dương ngoài 1 và chính nó (hay không có ước nguyên dương thực sự khác 1 ).

Yêu cầu: Cho số nguyên dương n , hãy liệt kê tất cả các số nguyên tố nhỏ hơn hoặc bằng n .

Dữ liệu vào:

  • Gồm một số nguyên dương n .

Dữ liệu ra:

  • Ghi ra trên một dòng các số nguyên tố nhỏ hơn hoặc bằng n , các số được ghi ra theo thứ tự tăng dần, hai số liên tiếp cách nhau một dấu cách.

Ví dụ:

Dữ liệu vào:
3
Dữ liệu ra:
2 3
Dữ liệu vào:
10
Dữ liệu ra:
2 3 5 7

Giới hạn:

  • 1 ≤ n ≤ 10^6 .