Liczenie liczb pierwszych

Napisz funkcję countPrimes, która otrzymuje liczbę całkowitą n i zwraca liczbę liczb pierwszych mniejszych od n.

Uwaga: złożoność czasowa musi być lepsza niż O(nlogn)

1 <= n <= 1000000

Przykłady:

Dane wejściowe - 10

Oczekiwany wynik - 4

Wyjaśnienie - Istnieją 4 liczby pierwsze mniejsze od 10: 2, 3, 5, 7

Dane wejściowe - 13

Oczekiwany wynik - 5

Wyjaśnienie - Istnieje 5 liczb pierwszych mniejszych od 13: 2, 3, 5, 7, 11 - pamiętaj, że 13 się nie liczy!