Đếm số nguyên tố nhỏ hơn hoặc bằng N bằng sàng
Khi cần biết *có bao nhiêu* số nguyên tố trong một khoảng, kiểm tra từng số bằng thử chia sẽ tốn O(N√(N)). Sàng Eratosthenes đánh dấu bội số của từng số nguyên tố và đưa chi ph…
Tiến độ của tôi ở bài này
Điểm được lưu vào tài khoản sau khi chấm bài.
Đang tải điểm của bạn…
Kiến thức và chủ đề
Kiến thức tiên quyết: arrays-and-loops, prime-check.
Nội dung đề bài
Mô tả bài toán
Khi cần biết *có bao nhiêu* số nguyên tố trong một khoảng, kiểm tra từng số bằng thử chia sẽ tốn O(N√(N)). Sàng Eratosthenes đánh dấu bội số của từng số nguyên tố và đưa chi phí về O(N log log N).
Yêu cầu
Đọc từ stdin một số nguyên N và in ra số lượng số nguyên tố p thoả 2 ≤ p ≤ N.
Quy ước nộp bài
- Chỉ cần viết một chương trình đọc
stdinvà in rastdout. Bài này không yêu cầu viết hàm. - Không truyền lời nhắc vào
input(). Lời nhắc sẽ bị in vàostdoutvà làm bài sai. - Chỉ in đúng nội dung ở mục Output. Không in thêm nhãn, dòng trống hay ký tự thừa.
- Output được so khớp từng ký tự, phân biệt chữ hoa/thường và dấu câu.
Input
Một dòng chứa số nguyên N.
Output
Một số nguyên: số lượng số nguyên tố không vượt quá N.
Ràng buộc
- 0 ≤ N ≤ 2 · 106.
- Thời gian chạy tối đa: 1000ms. Giới hạn bộ nhớ: 256MB.
Ví dụ 1
Input
10Output
4
Các số nguyên tố không vượt quá 10 là 2, 3, 5, 7 — được 4 số.Ví dụ 2
Input
1Output
0
Không có số nguyên tố nào $\le 1$.Gợi ý và lời giải chỉ mở sau khi bạn bấm Nộp bài. Giáo viên và quản trị viên mở được ngay.
Góp ý & báo lỗi bài tập
Đề bài chưa rõ, test có vấn đề hay bạn có ý tưởng giúp bài tốt hơn? Gửi cho đội ngũ AI Empire nhé — mỗi góp ý đều được đọc.