What is the Sieve of Eratosthenes?

The Sieve of Eratosthenes is an ancient and asymptotically optimal algorithm for finding all prime numbers up to any given limit n. It iteratively marks the multiples of each prime starting from $2$ as composite (not prime).

---

C Code Implementation

c (ISO Standard)
Run in Compiler.cCopy
#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>
#include <string.h>

void sieveOfEratosthenes(int n) {
    if (n < 2) {
        printf("No primes exist below 2.\n");
        return;
    }

    bool *isPrime = (bool*)malloc((n + 1) * sizeof(bool));
    if (isPrime == NULL) {
        fprintf(stderr, "Memory allocation failed.\n");
        return;
    }

    /* Initialize all entries as true */
    memset(isPrime, true, (n + 1) * sizeof(bool));
    isPrime[0] = isPrime[1] = false;

    for (int p = 2; p * p <= n; p++) {
        if (isPrime[p]) {
            /* Mark multiples of p starting at p*p */
            for (int i = p * p; i <= n; i += p) {
                isPrime[i] = false;
            }
        }
    }

    printf("Prime numbers up to %d:\n", n);
    int count = 0;
    for (int p = 2; p <= n; p++) {
        if (isPrime[p]) {
            printf("%d ", p);
            count++;
        }
    }
    printf("\nTotal primes found: %d\n", count);

    free(isPrime);
}

int main() {
    int limit = 50;
    sieveOfEratosthenes(limit);
    return 0;
}

Sample Output

text (ISO Standard)
Copy
Prime numbers up to 50:
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 
Total primes found: 15

---

Complexity Analysis

• Time Complexity: $O(n \log(\log n))$ — Highly optimized prime generation.
• Space Complexity: O(n) heap allocation for the boolean lookup sieve.

---

Related Programs

• Single number primality test in Prime Number Program in C.
• Master dynamic memory in Dynamic Memory Allocation in C.