Vansh Aggarwal

Posted on Apr 2

LeetCode Solution: 204. Count Primes

#leetcode #dsa #programming #tutorial

Unlock the Primes: Your First Dive into Counting Primes (LeetCode 204)

Hey there, future coding rockstars! 👋

Vansh2710 here, your friendly neighborhood competitive programmer and technical writer. Today, we're going to tackle a classic LeetCode problem that's super common in interviews and a fantastic way to learn about efficient algorithms: Problem 204: Count Primes.

Don't let the "mathy" title scare you! We'll break it down piece by piece, find an awesome solution, and make sure you walk away feeling like a prime number pro. Ready? Let's dive in!

Problem Explanation: What are we actually counting?

The problem asks us to do one simple thing: given an integer n, return the number of prime numbers that are strictly less than n.

"Strictly less than n" means we're looking at numbers from 0 up to n-1.

Let's look at a few examples to make it crystal clear:

Example 1: n = 10
- Numbers strictly less than 10 are: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9.
- Which of these are prime? A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself.
- The primes are: 2, 3, 5, 7.
- So, the output is 4.
Example 2: n = 0
- Numbers strictly less than 0? None!
- Output: 0.
Example 3: n = 1
- Numbers strictly less than 1? Only 0.
- Is 0 prime? No, primes must be greater than 1.
- Output: 0.

Simple enough, right? The core challenge is how to count these primes efficiently, especially when n can be as large as 5 * 10^6.

Intuition: From Naive to "Aha!" Moment 💡

Before we jump into the best solution, let's think about how we might naively solve this.

Naive Approach:

Start a counter for primes, initialized to 0.
Loop through every number i from 2 up to n-1.
For each i, check if it's prime. How? By trying to divide i by every number j from 2 up to sqrt(i). If i is divisible by any j (meaning i % j == 0), then i is not prime. If it's not divisible by any j, then i is prime, and we increment our counter.

This approach works, but it's incredibly slow. Imagine n is 5 * 10^6. For each number up to n, you're doing another loop that goes up to its square root. The total operations would be roughly n * sqrt(n), which for n = 5 * 10^6 is a massive number (~10 billion operations!). This will definitely give us a "Time Limit Exceeded" (TLE) error on LeetCode.

The "Aha!" Moment - The Sieve of Eratosthenes

What if, instead of repeatedly checking divisibility for each number, we could mark off non-prime numbers more efficiently?

This is where the ancient Greek mathematician Eratosthenes comes in with his brilliant "sieve" method. Think of it like a strainer:

Imagine you have a list of all numbers up to n-1. Initially, assume they are all prime.
Start with the first prime number, 2.
Aha! If 2 is prime, then all its multiples (4, 6, 8, 10, ...) cannot be prime! Let's mark them as non-prime.
Move to the next unmarked number. That's 3.
Aha again! If 3 is unmarked, it must be prime. All its multiples (6, 9, 12, 15, ...) cannot be prime. Mark them off! (Note: 6 was already marked by 2, which is fine.)
Continue this process. The numbers that remain unmarked must be prime.

This is the Sieve of Eratosthenes, and it's super efficient for finding all primes up to a given limit!

Approach: Sieving Our Way to Primes

Let's formalize the Sieve of Eratosthenes step-by-step:

Initialize a boolean array: Create an array, let's call it is_prime, of size n. Initialize all its elements to true. is_prime[i] will be true if i is considered prime, and false otherwise.
Handle Base Cases:
- Numbers 0 and 1 are not prime. So, set is_prime[0] = false and is_prime[1] = false.
The Sieving Process:
- Loop through numbers p starting from 2 up to sqrt(n). Why sqrt(n)? Because if a number k has a prime factor larger than sqrt(k), it must also have a prime factor smaller than sqrt(k). So, by the time we reach sqrt(n), all composite numbers less than n will have already been marked by their smaller prime factors.
- Inside this loop, check if is_prime[p] is true.
  - If is_prime[p] is true, it means p is a prime number.
  - Now, mark all multiples of p as not prime. Start marking from p * p up to n-1, with increments of p.
    - Why start from p * p? Because any multiple k * p where k < p would have already been marked by a smaller prime factor k. For example, when p=3, we don't need to mark 3*2=6 because 6 would have already been marked when p=2. We only need to mark 3*3=9, 3*4=12, and so on.
Count the Primes:
- After the sieving process is complete, iterate through the is_prime array from index 2 up to n-1.
- Count how many is_prime[i] values are still true. This count is your answer!

Let's walk through n = 10 again with the Sieve:

is_prime array of size 10: [T, T, T, T, T, T, T, T, T, T]
Mark 0 and 1 as false: [F, F, T, T, T, T, T, T, T, T]
Sieving Loop (p up to sqrt(10) ≈ 3):
- p = 2:
  - is_prime[2] is T. So, 2 is prime.
  - Mark multiples of 2 starting from 2*2=4:
    - is_prime[4] = F
    - is_prime[6] = F
    - is_prime[8] = F
  - Array becomes: [F, F, T, T, F, T, F, T, F, T]
- p = 3:
  - is_prime[3] is T. So, 3 is prime.
  - Mark multiples of 3 starting from 3*3=9:
    - is_prime[9] = F
  - Array becomes: [F, F, T, T, F, T, F, T, F, F]
Loop ends (next p would be 4, 4 > sqrt(10)).
Count: Iterate from i = 2 to 9:
- is_prime[2] is T (count = 1)
- is_prime[3] is T (count = 2)
- is_prime[5] is T (count = 3)
- is_prime[7] is T (count = 4)
- Total count: 4. Perfect!

Code 🧑‍💻

Here's the C implementation of the Sieve of Eratosthenes:

#include <stdbool.h> // For boolean type
#include <stdlib.h>  // For malloc

int countPrimes(int n) {
    // Handle edge cases where n is too small to contain any primes
    if (n <= 2) {
        return 0;
    }

    // Create a boolean array `is_prime` of size `n`
    // Initialize all entries as true. A value of true at `is_prime[i]`
    // will mean that i is potentially prime.
    bool *is_prime = (bool *)malloc(sizeof(bool) * n);
    if (is_prime == NULL) {
        // Handle memory allocation failure
        return -1; // Or throw an error, depending on desired behavior
    }

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

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

    // Start the Sieve process from p = 2
    // We only need to iterate up to sqrt(n)
    // Note: The loop condition `p * p < n` works because if `p` exceeds `sqrt(n)`,
    // then `p*p` would exceed `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]) {
            // Mark all multiples of p as not prime.
            // Start from p*p, because smaller multiples (like 2*p, 3*p, etc.)
            // would have already been marked by their smaller prime factors (2, 3, etc.).
            for (int i = p * p; i < n; i += p) {
                is_prime[i] = false;
            }
        }
    }

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

    // Free the dynamically allocated memory
    free(is_prime);
    is_prime = NULL; // Good practice to set pointer to NULL after freeing

    return count;
}

Time & Space Complexity Analysis

Understanding how efficient our algorithm is crucial in competitive programming.

Time Complexity: O(n log log n)
- The outer loop runs up to sqrt(n).
- The inner loop (marking multiples) runs for n/p times for each prime p.
- The total number of operations is approximately n/2 + n/3 + n/5 + ... for all primes p up to n. This sum is mathematically proven to be O(n log log n).
- For n = 5 * 10^6, log log n is a very small factor (around 2-3). This makes the Sieve extremely fast, almost linear O(n). Much better than O(n * sqrt(n))!
Space Complexity: O(n)
- We use a boolean array is_prime of size n to store the primality status of each number. This requires n boolean values, leading to O(n) space complexity.

Key Takeaways

Sieve of Eratosthenes: This is the go-to algorithm for finding all prime numbers up to a given limit n. Memorize its logic!
Optimization is Key: The naive approach is easy to think of but too slow for larger inputs. Understanding how to optimize, like marking multiples instead of repeated division checks, is fundamental.
Square Root Optimization: The p * p < n (or p < sqrt(n)) condition for the outer loop is a common optimization trick in primality tests and sieving algorithms.
Memory Management (C/C++): Remember to malloc memory for dynamic arrays and free it when you're done to prevent memory leaks!

And that's it! You've successfully conquered the Count Primes problem using a powerful and elegant algorithm. Give yourself a pat on the back!

Authored by Vansh2710 | Published: 2026-04-02 23:19:43

DEV Community