Example: Sieve of Eratosthenes Prime Finder in C

// Sieve of Eratosthenes Prime Finder
#include <stdio.h>
#include <stdbool.h> // For boolean type
#include <stdlib.h>  // For malloc

int main() {
    int lower_bound, upper_bound;

    // Step 1: Get user input for the range
    printf("Enter the lower bound of the range: ");
    scanf("%d", &lower_bound);
    printf("Enter the upper bound of the range: ");
    scanf("%d", &upper_bound);

    // Step 2: Create a boolean array `is_prime` up to upper_bound + 1
    // Initialize all entries to true (assuming they are prime)
    bool *is_prime = (bool *)malloc((upper_bound + 1) * sizeof(bool));
    if (is_prime == NULL) {
        printf("Memory allocation failed!\n");
        return 1;
    }

    for (int i = 0; i <= upper_bound; i++) {
        is_prime[i] = true;
    }

    // Step 3: Mark 0 and 1 as not prime
    if (upper_bound >= 0) is_prime[0] = false;
    if (upper_bound >= 1) is_prime[1] = false;

    // Step 4: Apply the Sieve algorithm
    // Start from p=2. If is_prime[p] is true, then p is prime.
    // Mark all multiples of p (p*p, p*p+p, ...) as not prime.
    for (int p = 2; p * p <= upper_bound; p++) {
        // If is_prime[p] is still true, then it is a prime
        if (is_prime[p] == true) {
            // Mark all multiples of p as not prime
            for (int i = p * p; i <= upper_bound; i += p)
                is_prime[i] = false;
        }
    }

    // Step 5: Print prime numbers in the specified range
    printf("Prime numbers between %d and %d are: ", lower_bound, upper_bound);
    for (int num = lower_bound; num <= upper_bound; num++) {
        if (is_prime[num]) {
            printf("%d ", num);
        }
    }
    printf("\n");

    // Step 6: Free the allocated memory
    free(is_prime);

    return 0;
}