Sieve of Eratosthenes in C (Fast Prime Generation)

The Sieve of Eratosthenes generates all prime numbers up to N in O(N log log N) time. Learn prime filtering, array marking, and integer overflow avoidance in C.

The Sieve of Eratosthenes is an ancient and remarkably efficient algorithm for finding all prime numbers up to a specified integer N in O(N log log N) time.

The algorithm initializes a boolean array marking all numbers as prime, then iteratively crosses off multiples of each discovered prime starting from 2. An important optimization is starting the crossing-off process at p * p, because smaller multiples will have already been eliminated by earlier prime factors.

In C, using a byte-level bool array or bitmask array minimizes cache pressure and memory footprint, allowing modern CPUs to find millions of primes within milliseconds.

Interactive Runnable C Implementation

#include <stdio.h>
#include <stdbool.h>
#include <string.h>

void sieve(int n) {
    bool isPrime[n + 1];
    memset(isPrime, true, sizeof(isPrime));

    for (int p = 2; p * p <= n; p++) {
        if (isPrime[p]) {
            for (int i = p * p; i <= n; i += p)
                isPrime[i] = false;
        }
    }

    printf("Primes up to %d:\n", n);
    for (int p = 2; p <= n; p++) {
        if (isPrime[p]) printf("%d ", p);
    }
    printf("\n");
}

int main() {
    int n = 50;
    sieve(n);
    return 0;
}

Open example in compiler

Expected Output

Primes up to 50:
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47