A few years back, I was reviewing a pull request from a junior dev who was building a basic cryptography tool. He had written a function to find all prime numbers up to a million to generate a key set. His approach was the "obvious" one: a loop from 2 to 1,000,000, and inside that, another loop checking for divisors. When I ran it on my machine, the fans kicked in, and it took several seconds to finish. I told him, "You're asking the computer to do a million separate math problems. Instead, let's just cross out the wrong answers." We switched to a sieve, and the execution time dropped from seconds to a few milliseconds. That's the power of shifting your algorithmic perspective.

Thinking in Multiples, Not Divisions

Most people start with primality testing—checking if a specific number is prime by dividing it by everything up to its square root. That's fine for one number. But when you need a range, that's incredibly wasteful. The Sieve of Eratosthenes flips the script. Instead of asking "Is this number prime?", we ask "Which numbers are definitely not prime?"

Imagine a giant grid of numbers. You start at 2, the first prime. You don't just note that 2 is prime; you immediately jump through the grid and mark every multiple of 2 (4, 6, 8...) as "composite." Then you move to the next unmarked number, 3, and mark all its multiples (6, 9, 12...). By the time you've reached the square root of your limit, every number left unmarked is guaranteed to be prime. It's a process of elimination that trades a bit of memory for a massive gain in speed.

Managing Memory with Boolean Maps

In C, the most efficient way to implement this is with an array of flags. While you could use an array of integers, that's a waste of space. I usually recommend char arrays or the bool type from <stdbool.h>. If you're looking for primes up to 10,000, you just need a boolean array of size 10,001. Each index represents the number itself.

// A quick glimpse at the core logic
bool is_prime[MAX_SIZE]; 
memset(is_prime, true, sizeof(is_prime)); // Assume everything is prime initially
is_prime[0] = is_prime[1] = false;        // 0 and 1 are special cases

for (int p = 2; p * p < MAX_SIZE; p++) {
    if (is_prime[p]) {
        // Start marking from p*p, because smaller multiples 
        // were already handled by previous primes
        for (int i = p * p; i < MAX_SIZE; i += p)
            is_prime[i] = false;
    }
}

One little optimization I want you to notice: the inner loop starts at p * p. If you're on the prime 5, you don't need to mark 10, 15, or 20, because 2 and 3 already took care of those. Starting at 25 saves a surprising amount of redundant work as the numbers get larger.

📋 Practical Task

Exercise: Building a Fast Prime-Finding Utility

Your task is to write a C program that implements the Sieve of Eratosthenes to find all prime numbers up to a user-defined limit. Instead of just printing them, your program must output the total count of primes found and the last prime number discovered below that limit.

Requirements:

• Use <stdbool.h> for your sieve array.
• The program should ask the user for an integer limit (e.g., 100,000).
• Use dynamic memory allocation (malloc) for the sieve array, as the user's limit might exceed the stack size.
• Ensure you properly free the allocated memory before the program exits.
• Implement the p * p optimization in your inner loop to maximize efficiency.