Math - Count Primes

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

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

Input: 0 → Output: 0

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.

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)