C Programming: The Sieve of Eratosthenes

Welcome to this comprehensive guide on C programming! Today, we'll be diving into one of the oldest known algorithms for finding prime numbers – The Sieve of Eratosthenes.

By the end of this tutorial, you'll understand the algorithm, its implementation in C, and how it can be optimized for real-world projects. Let's get started! 🎯

What is The Sieve of Eratosthenes?

📝 Note: The Sieve of Eratosthenes is an ancient algorithm used to find all prime numbers up to a given limit. It's named after the Greek astronomer and geographer, Eratosthenes.

This algorithm works by iteratively marking the multiples of each prime number, starting from 2. The numbers that remain unmarked are prime.

The Algorithm

Create a list of numbers from 2 to the square root of the given limit.
Begin with the first number (2) and mark all its multiples as composite (not prime).
Move to the next unmarked number and repeat the process until you've processed all numbers.
The remaining unmarked numbers are prime.

Implementation in C

Here's a simple implementation of the Sieve of Eratosthenes in C.

#include <stdio.h>

#define MAX 100

void sieve_of_eratosthenes(int primes[]) {
    bool is_composite[MAX] = {false};

    // Initialize the first prime number (2) as true
    is_composite[0] = true;

    for (int p = 4; p <= MAX; p += 2)
        is_composite[p] = true;

    for (int p = 3; p * p <= MAX; p += 2) {
        if (!is_composite[p]) {
            for (int i = p * p; i <= MAX; i += p * 2)
                is_composite[i] = true;
        }
    }

    // Store the prime numbers in an array
    int prime_count = 0;
    for (int i = 2; i <= MAX; i++) {
        if (!is_composite[i]) {
            primes[prime_count++] = i;
        }
    }
}

int main() {
    int primes[100];
    sieve_of_eratosthenes(primes);

    printf("Prime numbers up to %d:\n", MAX);
    for (int i = 0; i < 25; i++) {
        printf("%d ", primes[i]);
    }

    return 0;
}

💡 Pro Tip: This implementation uses an array is_composite to keep track of composite numbers. This helps optimize the algorithm by avoiding unnecessary checks.

Optimizing The Sieve of Eratosthenes

In practice, you may want to optimize the Sieve of Eratosthenes to handle larger numbers or to improve performance. One common optimization is to skip multiples of previously marked primes instead of iterating through them sequentially.

C Programming: The Sieve of Eratosthenes

C Programming: The Sieve of Eratosthenes

What is The Sieve of Eratosthenes?

The Algorithm

Implementation in C

Optimizing The Sieve of Eratosthenes

Quiz