Count Primes

Intuition

Instead of testing each number for primality on its own, flip the problem around and cross out composites. Keep a boolean array over the range and, for each number that is still unmarked when you reach it, treat it as prime and strike out all of its multiples. Starting the strike-out at the square of the prime avoids redundant work, since any smaller multiple already carries a smaller prime factor that marked it earlier. Whatever survives the sweep is prime.

Algorithm walkthrough

1. 1If n is less than 3 there are no primes below it, so return 0 right away.
2. 2Create a boolean array composite of length n, all initially false.
3. 3Scan i from 2 up to n - 1; whenever composite[i] is still false, count it as prime.
4. 4For each such prime i, mark every multiple starting at i * i up to n - 1 as composite.
5. 5Return the running count of unmarked numbers.

Implementation

class Solution:
    def countPrimes(self, n: int) -> int:
        if n < 3:
            return 0
        composite = [False] * n
        count = 0
        for i in range(2, n):
            if not composite[i]:
                count += 1
                for multiple in range(i * i, n, i):
                    composite[multiple] = True
        return count