Count Primes

Given an integer n, return the number of prime numbers that are strictly less than n.

Example 1

Input: 10 → Output: 4 (2, 3, 5, 7)

Example 2

Input: 0 → Output: 0

Solution Approach

Sieve of Eratosthenes: mark multiples of each prime as composite.

Create boolean isComposite[] of size n.
For each i from 2 to sqrt(n): if not composite, mark all multiples i*i, i*i+i, ... as composite.
Count non-composite numbers.

Java

class Solution {
    public int countPrimes(int n) {
        if (n <= 2) return 0;
        boolean[] composite = new boolean[n];
        for (int i = 2; (long)i*i < n; i++) {
            if (!composite[i])
                for (int j = i*i; j < n; j += i) composite[j] = true;
        }
        int count = 0;
        for (int i = 2; i < n; i++) if (!composite[i]) count++;
        return count;
    }
}

Time Complexity: O(N log log N)
Space Complexity: O(N)