Vansh Aggarwal

Posted on Apr 2

LeetCode Solution: 204. Count Primes

#leetcode #dsa #programming #tutorial

Unleashing the Power of Primes: Your First Sieve of Eratosthenes Adventure!

Hey there, future coding rockstars! 👋 Vansh here, ready to dive into another exciting LeetCode challenge with you. Today, we're tackling a classic problem that's super common in interviews and a fantastic way to learn about optimizing your code: 204. Count Primes.

Don't let the name scare you! We're going to break it down, understand the "aha!" moment, and build a super-efficient solution together. Ready? Let's roll!

🚀 The Problem Explained: Counting Our Prime Friends

Imagine you're at a party, and you need to count all the "special" guests. In our coding world, these special guests are prime numbers.

The problem asks us to:
Given an integer n, return the number of prime numbers that are strictly less than n.

What's a Prime Number?
A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself.

2, 3, 5, 7, 11 are primes.
4 (divisible by 2), 6 (divisible by 2, 3), 9 (divisible by 3) are NOT primes.

Let's look at the examples:

Example 1: n = 10
- We need primes less than 10.
- Primes: 2, 3, 5, 7
- Output: 4
Example 2: n = 0
- Primes are greater than 1. No primes less than 0.
- Output: 0
Example 3: n = 1
- No primes less than 1.
- Output: 0

The constraint 0 <= n <= 5 * 10^6 tells us that n can be quite large, hinting that a simple, brute-force approach might be too slow. This is where our optimization journey begins!

🤔 Intuition: From Naive to Nimble!

So, how would you first approach this?

First thought (The Naive Way):
"Okay, I'll just check every number from 2 up to n-1. For each number, I'll test if it's prime. How do I test if a number k is prime? I'll try dividing k by numbers from 2 up to sqrt(k). If none of them divide k evenly, then k is prime!"

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

// Helper function isPrime(k):
// for (j from 2 to sqrt(k)):
//     if (k % j == 0):
//         return false
// return true

This approach works! But let's think about efficiency. If n is 5 * 10^6, checking 5 * 10^6 numbers, and for each, doing sqrt(5 * 10^6) divisions... that's going to be astronomically slow! We need something much faster.

The "Aha!" Moment (The Sieve of Eratosthenes):

Instead of checking each number individually, what if we could eliminate non-prime numbers systematically?

Imagine you have a list of all numbers from 2 to n-1.

Start with the first prime number we know: 2.
Since 2 is prime, we know all its multiples (4, 6, 8, 10, 12...) cannot be prime. Let's cross them out!
Move to the next number that hasn't been crossed out: 3.
Since 3 is prime, cross out all its multiples (6, 9, 12, 15...). Notice that 6 and 12 were already crossed out by 2 – that's perfectly fine!
Move to the next unmarked number: 5. (4 was crossed out by 2). Cross out its multiples (10, 15, 20...).
Keep repeating this process!

By the end, any number that is not crossed out must be prime! This brilliant technique is called the Sieve of Eratosthenes, and it's perfect for finding all primes up to a certain limit.

💡 Approach: The Sieve in Action!

Let's walk through the steps of implementing the Sieve of Eratosthenes:

Initialize a "Primes Tracker":
- Create a boolean array (or an integer array where 1 means true and 0 means false) called is_prime of size n.
- Initialize all entries from is_prime[2] to is_prime[n-1] as true (or 1), assuming they are prime for now.
- is_prime[0] and is_prime[1] should be false (or 0), because 0 and 1 are not prime.
Start Sieving (The Main Loop):
- We'll iterate with a variable p starting from 2.
- The loop should continue as long as p * p < n. Why p * p? Because if p is a prime, all its multiples less than p * p (like p * 2, p * 3, up to p * (p-1)) would have already been marked as not prime by smaller prime factors. For example, multiples of 5 less than 25 (like 10, 15, 20) would have been marked by 2 or 3.
Marking Multiples:
- Inside the loop, if is_prime[p] is still true (meaning p itself is a prime number):
  - We know p is prime, so all its multiples are not prime.
  - Start another inner loop from i = p * p up to n-1, incrementing by p each time (i += p).
  - Set is_prime[i] = false (or 0) for all these multiples.
Count the Primes:
- After the main loop finishes, all numbers that are still marked true in our is_prime array are prime numbers.
- Iterate through the is_prime array from 2 up to n-1.
- For every is_prime[i] that is true, increment a count variable.
Return the Count:
- The final count is our answer!

Let's see this in C!

💻 Code: The Sieve in C

#include <stdlib.h> // Required for malloc and free

int countPrimes(int n) {
    // Handle edge cases: No primes less than or equal to 2
    if (n <= 2) {
        return 0;
    }

    // 1. Create a boolean array "is_prime[0...n-1]" and initialize
    //    all entries as true (represented by 1). A value in is_prime[i] will
    //    finally be false (0) if i is Not a prime, else true (1).
    //    Using an int array as a boolean array where 1=true, 0=false.
    int* is_prime = (int*)malloc(n * sizeof(int));
    if (is_prime == NULL) {
        // Handle memory allocation failure
        // For LeetCode, this typically won't happen for given constraints,
        // but good practice in real-world C code.
        return 0;
    }

    // Initialize all numbers to be potentially prime
    for (int i = 0; i < n; i++) {
        is_prime[i] = 1; // 1 means true (potentially prime)
    }

    // 0 and 1 are not prime numbers
    is_prime[0] = 0; // 0 means false (not prime)
    is_prime[1] = 0; // 0 means false (not prime)

    // 2. Start the Sieve process from p = 2
    //    We only need to iterate up to sqrt(n) because any composite number
    //    n must have a prime factor less than or equal to sqrt(n).
    for (int p = 2; p * p < n; p++) {
        // If is_prime[p] is still true, then it is a prime number
        if (is_prime[p] == 1) {
            // 3. Mark all multiples of p as not prime (false)
            //    We start marking from p*p because any multiple smaller than p*p
            //    (e.g., 2*p, 3*p, etc.) would have already been marked by a
            //    smaller prime factor (e.g., 2, 3).
            for (int i = p * p; i < n; i += p) {
                is_prime[i] = 0; // Mark as not prime
            }
        }
    }

    // 4. Count all prime numbers
    int count = 0;
    for (int i = 2; i < n; i++) {
        if (is_prime[i] == 1) {
            count++;
        }
    }

    // 5. Free the dynamically allocated memory
    free(is_prime);

    return count;
}

⏱️ Complexity Analysis

Understanding how efficient our algorithm is, is just as important as writing the correct code!

Time Complexity: O(N log log N)
- This might look intimidating, but it's incredibly efficient for finding all primes up to N.
- The outer loop runs up to sqrt(N).
- The inner loop (marking multiples) for each prime p iterates N/p times.
- When you sum N/p for all primes p up to N, it mathematically approximates to N log log N. This is much faster than O(N * sqrt(N)) of the naive approach!
Space Complexity: O(N)
- We use an array is_prime of size N to store the primality status of each number. This makes the space complexity directly proportional to N.

🎯 Key Takeaways

The Sieve of Eratosthenes: This is a fundamental algorithm for efficiently finding all prime numbers up to a specified limit. It's a must-know for competitive programming and interviews!
Trade-off: We use extra space (O(N) for the is_prime array) to achieve significantly faster time complexity (O(N log log N)). This is a common pattern in algorithm design!
Optimization p * p: Starting the inner loop from p * p is a crucial optimization that prevents redundant work and makes the sieve faster.
Problem Recognition: When you see problems asking for "all primes up to N" or "counting primes less than N" with large N, think Sieve!
Memory Management (in C/C++): Don't forget to free dynamically allocated memory (malloc) to prevent memory leaks!

Congratulations! You've just learned and implemented one of the coolest and most efficient prime-finding algorithms out there. Keep practicing, and you'll be a coding wizard in no time!

Happy coding! ✨

Authored by Vansh2710 | Published: 2026-04-02 23:25:05

DEV Community