Đếm số nguyên tố (sàng Eratosthenes)

Trung bình

số họcsàng nguyên tố7 test · 3 giây

Đếm số lượng số nguyên tố ≤ n.

Kiểm tra từng số là quá chậm với n = 5·10⁶. Hãy dùng sàng Eratosthenes: với mỗi số nguyên tố p, gạch bỏ các bội p², p² + p, …

Dữ liệu vào

Một số nguyên n (0 ≤ n ≤ 5·10⁶).

Số lượng số nguyên tố ≤ n.

Input

Output

Input

Output

# Đọc dữ liệu từ input(), in kết quả bằng print()
import sys

def main():
    data = sys.stdin.read().split()
    # TODO: xử lý


main()

# Đọc dữ liệu từ input(), in kết quả bằng print()
import sys

def main():
    data = sys.stdin.read().split()
    # TODO: xử lý


main()

Input (stdin)

Output

Bấm “Chạy thử” để xem kết quả với input bên trái.