LeetCode Solution: 204. Count Primes

#leetcode #dsa #programming #tutorial

Master the Sieve! Counting Primes Efficiently (LeetCode 204)

Hey there, aspiring competitive programmer! 👋 Vansh here, ready to tackle another classic LeetCode problem that's super common in interviews and a fantastic way to learn about algorithm optimization. Today, we're diving into problem 204: "Count Primes."

Don't let the name scare you! Prime numbers might sound complex, but the core idea is simple, and the trick to solving this efficiently is a beautiful algorithm called the Sieve of Eratosthenes. Let's unravel it together!

🌟 The Problem: Simple Yet Tricky!

Problem Statement: Given an integer n, your task is to return the count of prime numbers that are strictly less than n.

Wait, what's a prime number?
Great question! A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself.

Examples of primes: 2, 3, 5, 7, 11, 13, ...
Examples of non-primes (composite numbers): 4 (divisible by 2), 6 (divisible by 2, 3), 9 (divisible by 3), ...
Important: 0 and 1 are not considered prime numbers.

Let's look at the examples given:

Example 1: n = 10
- Numbers strictly less than 10 are: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9.
- Out of these, the primes are: 2, 3, 5, 7.
- Output: 4
Example 2: n = 0
- No numbers are strictly less than 0.
- Output: 0
Example 3: n = 1
- No numbers are strictly less than 1 that can be prime.
- Output: 0

The constraints tell us n can be up to 5 * 10^6. This hints that a simple, brute-force check for primality for every number won't be fast enough. We need something clever!

🤔 Intuition: From Brute-Force to "Aha!"

My first thought for checking if a number k is prime is to try dividing k by every number from 2 up to sqrt(k). If none of them divide k evenly, then k is prime.

If we apply this for every number from 2 up to n-1:

count = 0
for i from 2 to n-1:
    if isPrime(i):
        count++
return count

And isPrime(i) itself involves a loop. This approach quickly becomes too slow when n gets large (like 5 * 10^6). Think about it: for n=5*10^6, we'd be calling isPrime millions of times, and each call can involve thousands of divisions. 🐌

The "Aha!" Moment: Don't Repeat Work!

What if, instead of repeatedly checking divisibility, we could somehow mark non-prime numbers as we discover them?

Consider the number 2. It's prime!
Now, any multiple of 2 (4, 6, 8, 10, 12, ...) cannot be prime, because they are all divisible by 2. So, we can just mark them as not prime.

Next, consider 3. It's prime!
Any multiple of 3 (6, 9, 12, 15, ...) cannot be prime. We can mark them. (Notice 6 was already marked by 2 – that's fine!)

This filtering process, where you start with an assumption (all numbers are prime) and then systematically cross out multiples of known primes, is exactly what the Sieve of Eratosthenes does! It's like sifting flour – you start with everything and shake out the unwanted bits.

🚀 The Approach: Sieve of Eratosthenes Step-by-Step

The Sieve of Eratosthenes is an ancient and incredibly efficient algorithm for finding all prime numbers up to any given limit. Here's how we'll implement it:

Initialize a "Primes" List:
- Create a boolean array (or vector) called isPrime of size n.
- Initialize all entries to true. This means we initially assume all numbers from 0 to n-1 are prime.
Handle Non-Primes (0 and 1):
- We know 0 and 1 are not prime. So, immediately set isPrime[0] = false and isPrime[1] = false.
Sieve Process:
- Start a loop from p = 2 (the first prime number). This loop will go up to sqrt(n-1). Why sqrt(n-1)? Because if a number X has a divisor d > sqrt(X), then it must also have a divisor X/d < sqrt(X). So, we only need to check for prime factors up to the square root. Any composite number X will have already been marked false by one of its prime factors p <= sqrt(X).
- Inside the loop (for p):
  - Check if isPrime[p] is still true. If it is, p is a prime number!
  - Now, p is prime, so all its multiples are composite (not prime). We need to mark them as false.
  - Start another inner loop from i = p * p up to n-1, incrementing i by p (i += p).
    - Set isPrime[i] = false.
    - Why start from p * p? All multiples of p smaller than p * p (i.e., 2*p, 3*p, ..., (p-1)*p) would have already been marked by smaller prime factors. For example, 2*p would have been marked by 2, 3*p by 3, and so on. So, p*p is the first multiple that might not have been marked yet.
Count the Primes:
- After the sieving process is complete, iterate through the isPrime array from p = 2 up to n-1.
- For every index p where isPrime[p] is true, increment a count variable.
Return the Count:
- The final count is your answer!

Let's walk through n = 10 using this approach:

isPrime array of size 10: [T, T, T, T, T, T, T, T, T, T]
Mark 0 and 1: [F, F, T, T, T, T, T, T, T, T]
Sieve Loop (p from 2 up to sqrt(9) = 3):
- p = 2: isPrime[2] is T. So, 2 is prime!
  - Mark multiples of 2 from 2*2=4 up to 9 as F:
  - isPrime[4]=F, isPrime[6]=F, isPrime[8]=F
  - isPrime becomes: [F, F, T, T, F, T, F, T, F, T]
- p = 3: isPrime[3] is T. So, 3 is prime!
  - Mark multiples of 3 from 3*3=9 up to 9 as F:
  - isPrime[9]=F
  - isPrime becomes: [F, F, T, T, F, T, F, T, F, F]
- Loop ends because p would be 4, which is > sqrt(9).
Count Primes:
- isPrime[2] is T -> count = 1
- isPrime[3] is T -> count = 2
- isPrime[4] is F
- isPrime[5] is T -> count = 3
- isPrime[6] is F
- isPrime[7] is T -> count = 4
- isPrime[8] is F
- isPrime[9] is F
Return: 4. Perfect!

💻 Solution Code (C)

#include <stdbool.h>
#include <stdlib.h> // For malloc and free

int countPrimes(int n) {
    // Edge cases: 0, 1, 2 have no primes strictly less than them
    if (n <= 2) {
        return 0;
    }

    // 1. Initialize a boolean array 'isPrime' of size 'n'
    // and assume all numbers are prime initially.
    // Calloc initializes memory to zero (false for boolean)
    // We want true, so let's use malloc and then fill.
    bool* isPrime = (bool*)malloc(n * sizeof(bool));
    if (isPrime == NULL) {
        // Handle memory allocation failure
        return 0; // Or some error code
    }

    for (int i = 0; i < n; i++) {
        isPrime[i] = true;
    }

    // 2. Mark 0 and 1 as not prime
    isPrime[0] = false;
    isPrime[1] = false;

    // 3. Sieve Process
    // Loop from p = 2 up to sqrt(n-1)
    // p*p <= n is equivalent to p <= sqrt(n)
    for (long long p = 2; p * p < n; p++) {
        // If isPrime[p] is still true, then p is a prime number
        if (isPrime[p]) {
            // Mark all multiples of p as not prime
            // Start from p*p, as smaller multiples would have already been marked
            for (long long i = p * p; i < n; i += p) {
                isPrime[i] = false;
            }
        }
    }

    // 4. Count the primes
    int count = 0;
    for (int i = 2; i < n; i++) {
        if (isPrime[i]) {
            count++;
        }
    }

    // Free the dynamically allocated memory
    free(isPrime);
    isPrime = NULL;

    // 5. Return the total count
    return count;
}

⏰ Time & Space Complexity Analysis

Time Complexity: O(n log log n)
- Initializing the isPrime array takes O(n) time.
- The outer loop runs up to sqrt(n).
- The inner loop (marking multiples) is the key. For each prime p, it performs n/p operations.
- The sum of n/p for all primes p up to n is approximately n * (1/2 + 1/3 + 1/5 + ...) which is O(n log log n). This is highly efficient and much faster than O(n * sqrt(n))!
- Counting the primes takes O(n).
- Overall, the dominant factor is O(n log log n).
Space Complexity: O(n)
- We use a boolean array isPrime of size n to store the primality status of each number. This takes O(n) space. For n = 5 * 10^6, this is about 5 megabytes, which is perfectly acceptable.

🔑 Key Takeaways

Don't Brute-Force Primality for Ranges: If you need to find many primes up to a certain limit, the Sieve of Eratosthenes is almost always the way to go. Checking primality for each number individually is inefficient.
Sieve of Eratosthenes: Understand its core idea: start with all numbers as potentially prime, then systematically eliminate multiples of known primes.
Optimization p * p: Starting the marking of multiples from p * p is a crucial optimization. It avoids redundant work because smaller multiples would have already been marked by smaller prime factors.
Time Efficiency: The O(n log log n) complexity makes the Sieve extremely powerful for large inputs.
Memory Management (C/C++): Remember to malloc memory for dynamic arrays and free it after you're done to prevent memory leaks!

This problem is a fantastic entry point into number theory algorithms and demonstrates how a clever insight can dramatically improve performance. Keep practicing, and you'll be a master of these techniques in no time! Happy coding!

Author Account: Vansh2710
Time Published: 2026-04-02 23:14:04