How to Implement the Sieve of Eratosthenes in C

Introduction

In this lab, you will learn how to implement the Sieve of Eratosthenes algorithm in C to find prime numbers up to a given upper limit. You will start by reading the upper limit from the user, then mark multiples of prime numbers as non-prime, and finally print all the prime numbers found. This lab covers concepts in number theory and discrete mathematics using the C programming language.

The lab consists of three main steps: reading the upper limit, marking multiples as non-prime, and printing all prime numbers. By following these steps, you will gain a deeper understanding of the Sieve of Eratosthenes algorithm and its implementation in C.

Read Upper Limit

In this step, you will learn how to read the upper limit for the Sieve of Eratosthenes algorithm in C. The upper limit determines the range of prime numbers we want to find.

First, let's create a new C file for our implementation:

cd ~/project
nano prime_sieve.c

Now, let's write the initial code to read the upper limit:

#include <stdio.h>

int main() {
    int upper_limit;

    printf("Enter the upper limit for finding prime numbers: ");
    scanf("%d", &upper_limit);

    printf("Upper limit entered: %d\n", upper_limit);

    return 0;
}

Compile and run the program:

gcc prime_sieve.c -o prime_sieve
./prime_sieve

Example output:

Enter the upper limit for finding prime numbers: 50
Upper limit entered: 50

Let's break down the code:

We use scanf() to read an integer input from the user
The %d format specifier tells scanf() to read an integer
We store the input in the upper_limit variable
We then print the entered upper limit to confirm the input

Mark Multiples as Non-Prime

In this step, you will implement the core logic of the Sieve of Eratosthenes algorithm to mark multiples of prime numbers as non-prime.

Let's modify the previous prime_sieve.c file:

cd ~/project
nano prime_sieve.c

Update the code to include an array and mark multiples:

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

int main() {
    int upper_limit;

    printf("Enter the upper limit for finding prime numbers: ");
    scanf("%d", &upper_limit);

    // Create a boolean array to mark prime and non-prime numbers
    bool is_prime[upper_limit + 1];

    // Initialize all numbers as prime
    for (int i = 2; i <= upper_limit; i++) {
        is_prime[i] = true;
    }

    // Mark multiples of each prime number as non-prime
    for (int p = 2; p * p <= upper_limit; p++) {
        if (is_prime[p]) {
            // Mark multiples of p as non-prime
            for (int i = p * p; i <= upper_limit; i += p) {
                is_prime[i] = false;
            }
        }
    }

    printf("Marking multiples complete.\n");

    return 0;
}

Compile and run the program:

gcc prime_sieve.c -o prime_sieve
./prime_sieve

Example output:

Enter the upper limit for finding prime numbers: 50
Marking multiples complete.

Let's break down the Sieve of Eratosthenes logic:

We create a boolean array is_prime to track prime and non-prime numbers
Initially, all numbers are marked as prime
We iterate through numbers from 2 to sqrt(upper_limit)
For each prime number, we mark its multiples as non-prime
We start marking from p^2 to optimize the algorithm
The inner loop increments by p to mark all multiples of p

Print All Prime Numbers

In this step, you will complete the Sieve of Eratosthenes implementation by printing all the prime numbers found within the given range.

Let's modify the prime_sieve.c file to add the printing functionality:

cd ~/project
nano prime_sieve.c

Update the code to print prime numbers:

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

int main() {
    int upper_limit;

    printf("Enter the upper limit for finding prime numbers: ");
    scanf("%d", &upper_limit);

    // Create a boolean array to mark prime and non-prime numbers
    bool is_prime[upper_limit + 1];

    // Initialize all numbers as prime
    for (int i = 2; i <= upper_limit; i++) {
        is_prime[i] = true;
    }

    // Mark multiples of each prime number as non-prime
    for (int p = 2; p * p <= upper_limit; p++) {
        if (is_prime[p]) {
            // Mark multiples of p as non-prime
            for (int i = p * p; i <= upper_limit; i += p) {
                is_prime[i] = false;
            }
        }
    }

    // Print all prime numbers
    printf("Prime numbers up to %d are:\n", upper_limit);
    for (int p = 2; p <= upper_limit; p++) {
        if (is_prime[p]) {
            printf("%d ", p);
        }
    }
    printf("\n");

    return 0;
}

Compile and run the program:

gcc prime_sieve.c -o prime_sieve
./prime_sieve

Example output:

Enter the upper limit for finding prime numbers: 50
Prime numbers up to 50 are:
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47

Let's break down the final steps:

After marking multiples, we iterate through the is_prime array
We print only the numbers that remain marked as prime
The output shows all prime numbers up to the user-specified limit

Summary

In this lab, you first learned how to read the upper limit for the Sieve of Eratosthenes algorithm in C. You created a C file, prime_sieve.c, and wrote code to prompt the user for the upper limit and store it in the upper_limit variable. Then, you implemented the core logic of the Sieve of Eratosthenes algorithm by creating a boolean array to mark prime and non-prime numbers. You initialized all numbers as prime and then marked multiples of each prime number as non-prime. Finally, you will learn how to print all the prime numbers within the given upper limit.