Count Primes - Unveiling the Sieve of Eratosthenes (Java)

Introduction :

Today, we venture into the world of number theory with a classic problem: "Count Primes" (LeetCode #204). At first glance, counting primes might seem like a simple loop, but to do it efficiently for larger numbers, we need a smarter approach. This problem is the perfect introduction to a powerful algorithm called the Sieve of Eratosthenes. Let's uncover its elegant solution and understand its efficiency!

Understanding the Problem:

We are given an integer n. Our task is to return the number of prime numbers that are strictly less than n.

Important Definitions:

• A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself. (e.g., 2, 3, 5, 7, 11...).

• Strictly less than n means we count primes up to n-1.

Examples:

• Input: n = 10

  • Output: 4

  • Explanation: The primes less than 10 are 2, 3, 5, 7. (Total 4)

• Input: n = 0

  • Output: 0

• Input: n = 1

  • Output: 0

Constraints:

• 0 <= n <= 5 * 10^6 (This constraint immediately tells us a naive approach will be too slow!)

My Thought Process & Approach (The Sieve of Eratosthenes):

My initial thought for counting primes might be to loop from 2 up to n-1, and for each number, check if it's prime by trying to divide it by all numbers up to its square root. This "trial division" method would be very slow for large n (roughly O(N * sqrt(N))). Given n can be up to 5 * 10^6, N * sqrt(N) would be way too much!

This is where the Sieve of Eratosthenes comes to the rescue. It's an ancient, yet highly efficient, algorithm for finding all prime numbers up to a specified integer. The core idea is simple:

1. Assume All Numbers are Prime: Create a boolean array, isprime, of size n (or n+1 for 1-based indexing convenience), and initially mark all entries from 2 up to n-1 as true. (0 and 1 are not prime, so we can ignore them or mark them as false).

2. Start with the First Prime (2):

   • Since 2 is prime, all its multiples (4, 6, 8, 10, ...) cannot be prime. So, we iterate through its multiples (starting from 2*2 or p*p for optimization) and mark them as false in our isprime array.

3. Move to the Next Unmarked Number: Find the next number p that is still marked true in our isprime array. This number p must be prime (because if it had a smaller prime factor, it would have already been marked false).

4. Mark its Multiples: Once we find a prime p, we then mark all its multiples (p*p, p*p + p, p*p + 2p, ...) as false. We start marking from p*p because any smaller multiples (e.g., 2p, 3p) would have already been marked by smaller prime factors (2, 3, etc.).

5. Repeat: Continue this process for all numbers p up to sqrt(n). We only need to go up to sqrt(n) because if a number k has a prime factor greater than sqrt(n), it must also have a prime factor smaller than sqrt(n), which would have already marked k as non-prime.

6. Count Primes: After the sieving process, simply iterate through the isprime array from 2 to n-1 and count how many entries are still marked true.

This method efficiently eliminates composites, leaving only primes.

Java Code Implementation:

class Solution {
    public int countPrimes(int n) {
        boolean[] isprime = new boolean[n];
        Arrays.fill(isprime,true);
        if(n<2){
            return 0;
        }
        for(int p = 2;p*p<n;p++){
            if(isprime[p]){
                for(int i =p*p;i<n;i=i+p){
                        isprime[i] = false;
                }
            }
        }
        int cnt =0;
        for(int i =2;i<n;i++){
            if(isprime[i]){
                cnt++;
            }
        }
        return cnt;
    }
}

Time and Space Complexity Analysis:

• Time Complexity: O(N log log N)

  • This is the remarkable efficiency of the Sieve of Eratosthenes. The outer loop runs up to sqrt(N). The inner loop marks multiples. The sum of iterations for marking is roughly N/2 + N/3 + N/5 + ... for all primes up to N, which mathematically approximates to N * log(log(N)).

  • This is significantly faster than O(N * sqrt(N)) and allows it to pass for n up to 5 * 10^6.

• Space Complexity: O(N)

  • We use a boolean array isprime of size N. The space used grows linearly with the input N. This is necessary to keep track of the primality of all numbers up to N.