Approach

Count Primes

Approach

Use the Sieve of Eratosthenes algorithm to efficiently find all primes.

Algorithm

Create boolean array of size n, initially all true
Mark 0 and 1 as not prime
For each number i from 2 to √n:
- If i is marked prime:
  - Mark all multiples of i starting from i² as not prime
Count remaining numbers marked as prime

Complexity

Time: O(n log log n) - Sieve of Eratosthenes complexity
Space: O(n) - boolean array storage

Key Insights

Most efficient algorithm for finding multiple primes
Only need to check up to √n
Start marking from i² since smaller multiples already marked
Classic number theory algorithm

Solution

java

1class Solution {
2    public int countPrimes(int n) {
3        if (n <= 2) return 0;
4        
5        // Create boolean array, initially all true
6        boolean[] isPrime = new boolean[n];
7        Arrays.fill(isPrime, true);
8        isPrime[0] = isPrime[1] = false;  // 0 and 1 are not prime
9        
10        // Sieve of Eratosthenes
11        for (int i = 2; i * i < n; i++) {
12            if (isPrime[i]) {
13                // Mark all multiples of i as not prime
14                for (int j = i * i; j < n; j += i) {
15                    isPrime[j] = false;
16                }
17            }
18        }
19        
20        int count = 0;
21        for (boolean prime : isPrime) {
22            if (prime) count++;
23        }
24        
25        return count;
26    }
27}