Solutions

1. Brute Force

class Solution:
    def countPrimes(self, n: int) -> int:
        res = 0
        for num in range(2, n):
            isPrime = True
            for i in range(2, int(num ** 0.5) + 1):
                if num % i == 0:
                    isPrime = False
                    break
            if isPrime:
                res += 1
        return res

Time & Space Complexity

Time complexity: $O(n \sqrt {n})$
Space complexity: $O(1)$

2. Sieve of Eratosthenes

class Solution:
    def countPrimes(self, n: int) -> int:
        sieve = [False] * n
        res = 0
        for num in range(2, n):
            if not sieve[num]:
                res += 1
                for i in range(num * num, n, num):
                    sieve[i] = True
        return res

Time & Space Complexity

Time complexity: $O(n \log (\log n))$
Space complexity: $O(n)$

3. Sieve of Eratosthenes (Optimal)

class Solution:
    def countPrimes(self, n: int) -> int:
        if n < 3:
            return 0

        isPrime = [False] * n
        count = n // 2

        for i in range(3, int(n ** 0.5) + 1, 2):
            if not isPrime[i]:
                for j in range(i * i, n, 2 * i):
                    if not isPrime[j]:
                        isPrime[j] = True
                        count -= 1

        return count

Time & Space Complexity

Time complexity: $O(n \log (\log n))$
Space complexity: $O(n)$