Đếm số nguyên tố

Viết một hàm countPrimes nhận một số nguyên n và trả về số lượng số nguyên tố nhỏ hơn n.

Lưu ý: Độ phức tạp thời gian phải tốt hơn O(nlogn)

1 <= n <= 1000000

Ví dụ:

Đầu vào - 10

Đầu ra mong đợi - 4

Giải thích - Có 4 số nguyên tố nhỏ hơn 10: 2, 3, 5, 7

Đầu vào - 13

Đầu ra mong đợi - 5

Giải thích - Có 5 số nguyên tố nhỏ hơn 13: 2, 3, 5, 7, 11 - lưu ý rằng 13 không được tính!