Mô tả
Tại Viện Di truyền Nông nghiệp, các nhà nghiên cứu đang thu thập các hạt thóc giống lúa siêu chuẩn để lai tạo giống mới. Họ sắp xếp N hạt thóc trên một khay dài, đánh số thứ tự từ 1 đến N.
Quy trình lọc diễn ra theo nguyên lý Eratosthenes: bắt đầu từ hạt số 2 (hạt giống tốt nhất), họ sẽ "quét" (loại bỏ) tất cả các bội số của 2 (4, 6, 8, ...). Sau đó, họ tìm hạt tiếp theo chưa bị quét (số 3) và tiếp tục quét các bội của nó (9, 15, ...). Quá trình cứ tiếp tục cho đến khi không còn hạt nào để lọc.
Các hạt còn sót lại chính là các hạt giống lúa siêu chuẩn. Nhiệm vụ của bạn là: cho trước số nguyên dương N, hãy tính xem sau khi thực hiện quy trình lọc trên, có bao nhiêu hạt giống lúa siêu chuẩn còn sót lại.
Đầu vào
- Một số nguyên dương N (2 ≤ N ≤ 10^6), là số lượng hạt thóc trên khay.
Đầu ra
- Một số nguyên duy nhất, là số lượng hạt giống lúa siêu chuẩn còn lại.
Ràng buộc
- 2 ≤ N ≤ 10^6
- Độ phức tạp thời gian mục tiêu: O(N log log N).
Ví dụ
Ví dụ 1:
- Đầu vào:
10 - Đầu ra:
4
Giải thích: Khay có 10 hạt. Lọc số 2, loại 4, 6, 8, 10. Lọc số 3, loại 9. Số 4 đã bị loại. Hạt số 5 còn nguyên, loại 10 (đã bị loại). Các bội của 7 đều > 10 nên dừng. Các hạt còn sót là 2, 3, 5, 7 — tổng cộng 4 hạt.
Ví dụ 2:
- Đầu vào:
2 - Đầu ra:
1
Giải thích: Khay chỉ có 2 hạt. Hạt số 1 không được tính, hạt số 2 không có bội số trong khoảng. Kết quả là 1 hạt giống.