C Program To Find All Prime Numbers In A Given Range

Prime numbers are fundamental building blocks in mathematics, playing a crucial role in various computational and theoretical applications. In this article, you will learn how to identify and list all prime numbers within a specified numerical range using different C programming approaches.

Problem Statement

A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself. The problem is to develop C programs that can efficiently find and display all such prime numbers within a user-defined lower and upper bound. For instance, if the range is 10 to 20, the expected output would be 11, 13, 17, 19.

Example

Consider finding prime numbers in the range 10 to 30.

The output would be:

Prime numbers between 10 and 30 are: 11 13 17 19 23 29

Background & Knowledge Prerequisites

To understand the solutions presented, readers should have a basic understanding of:

• C Programming Basics: Variables, data types, input/output operations (printf, scanf).
• Control Flow: for and while loops, if-else conditional statements.
• Operators: Arithmetic operators, comparison operators, modulo operator (%).

Use Cases or Case Studies

Prime numbers are not just mathematical curiosities; they have critical applications in various fields:

• Cryptography: Prime numbers are the foundation of public-key cryptography algorithms like RSA, which secure online communications and transactions.
• Hashing: They are often used in hash function design to minimize collisions and ensure even distribution of data in hash tables.
• Pseudorandom Number Generation: Some algorithms for generating sequences of numbers that appear random rely on properties of prime numbers.
• Number Theory Research: Prime numbers are a central topic in number theory, with ongoing research into their distribution and properties (e.g., Riemann Hypothesis).
• Error Correction Codes: Certain error-correcting codes, used in data storage and transmission, utilize finite fields based on prime numbers.

Solution Approaches

We will explore three distinct methods to find prime numbers within a given range, progressing from simpler to more efficient algorithms.

Approach 1: Naive Trial Division

This approach checks every number in the given range. For each number, it iterates from 2 up to number - 1 to see if any of these divisors evenly divide the number. If no divisors are found, the number is prime.

// Naive Prime Number Finder
#include <stdio.h>
#include <stdbool.h> // For boolean type

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);

    printf("Prime numbers between %d and %d are: ", lower_bound, upper_bound);

    // Step 2: Iterate through each number in the range
    for (int num = lower_bound; num <= upper_bound; num++) {
        // Step 3: Handle special cases: numbers less than 2 are not prime
        if (num <= 1) {
            continue; // Skip numbers that are 1 or less
        }

        // Step 4: Check for divisibility from 2 up to num-1
        bool is_prime = true;
        for (int i = 2; i < num; i++) {
            if (num % i == 0) {
                is_prime = false; // Found a divisor, so not prime
                break;            // No need to check further
            }
        }

        // Step 5: If no divisors were found, print the number
        if (is_prime) {
            printf("%d ", num);
        }
    }
    printf("\\n");

    return 0;
}

Run

Sample Output:

Enter the lower bound of the range: 10
Enter the upper bound of the range: 30
Prime numbers between 10 and 30 are: 11 13 17 19 23 29

Stepwise Explanation:

1. The program first prompts the user to enter the lower and upper bounds of the desired range.
2. It then enters a for loop that iterates through each integer num from lower_bound to upper_bound.
3. Inside the loop, it first checks if num is 1 or less. If so, it skips to the next number as primes must be greater than 1.
4. For each num > 1, a boolean flag is_prime is initialized to true. A nested for loop then checks for divisibility from i = 2 up to num - 1.
5. If num is perfectly divisible by any i (i.e., num % i == 0), it means num has a divisor other than 1 and itself, so is_prime is set to false, and the inner loop breaks.
6. After the inner loop completes, if is_prime is still true, num is printed as a prime number.

Approach 2: Optimized Trial Division (up to Square Root)

This is an optimization of the naive trial division. A number num only needs to be checked for divisibility by integers up to its square root. If num has a divisor greater than its square root, it must also have a divisor smaller than its square root.

// Optimized Prime Number Finder
#include <stdio.h>
#include <stdbool.h> // For boolean type
#include <math.h>    // For sqrt() function

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);

    printf("Prime numbers between %d and %d are: ", lower_bound, upper_bound);

    // Step 2: Iterate through each number in the range
    for (int num = lower_bound; num <= upper_bound; num++) {
        // Step 3: Handle special cases: numbers less than 2 are not prime
        if (num <= 1) {
            continue;
        }
        // Handle 2 separately, as it's the only even prime
        if (num == 2) {
            printf("%d ", num);
            continue;
        }
        // Skip even numbers greater than 2 immediately
        if (num % 2 == 0) {
            continue;
        }

        // Step 4: Check for divisibility from 3 up to sqrt(num), only odd divisors
        bool is_prime = true;
        // Optimization: check divisors only up to sqrt(num)
        int limit = (int)sqrt(num); 
        for (int i = 3; i <= limit; i += 2) { // Check only odd divisors
            if (num % i == 0) {
                is_prime = false;
                break;
            }
        }

        // Step 5: If no divisors were found, print the number
        if (is_prime) {
            printf("%d ", num);
        }
    }
    printf("\\n");

    return 0;
}

Run

Sample Output:

Enter the lower bound of the range: 10
Enter the upper bound of the range: 30
Prime numbers between 10 and 30 are: 11 13 17 19 23 29

Stepwise Explanation:

1. Similar to the first approach, the program takes the range as input.
2. It iterates through each num in the range, handling num <= 1 and num == 2 as special cases.
3. A significant optimization is added: if num is an even number greater than 2, it's immediately skipped because it cannot be prime.
4. For odd numbers, the inner loop now checks for divisibility only by odd numbers i starting from 3, up to the integer part of sqrt(num). This drastically reduces the number of division operations.
5. If num remains prime after these checks, it is printed.

Approach 3: Sieve of Eratosthenes

The Sieve of Eratosthenes is a highly efficient algorithm for finding all prime numbers up to a specified limit. It works by iteratively marking as composite (not prime) the multiples of each prime, starting with the first prime number, 2.

// 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;
}

Run

Sample Output:

Enter the lower bound of the range: 10
Enter the upper bound of the range: 30
Prime numbers between 10 and 30 are: 11 13 17 19 23 29

Stepwise Explanation:

1. The program takes the lower_bound and upper_bound of the range.
2. It dynamically allocates a boolean array is_prime of size upper_bound + 1. All elements are initially set to true, assuming all numbers are prime.
3. is_prime[0] and is_prime[1] are set to false because 0 and 1 are not prime.
4. The core Sieve algorithm starts:

• It iterates from p = 2 up to sqrt(upper_bound).
• If is_prime[p] is true, it means p is a prime number.
• Then, all multiples of p (starting from p*p) up to upper_bound are marked as false in the is_prime array, as they are composite.

1. Finally, the program iterates from lower_bound to upper_bound and prints any number num for which is_prime[num] is true.
2. The dynamically allocated memory for is_prime is freed.

Conclusion

Finding prime numbers within a range can be accomplished using various algorithms, each with its own trade-offs between simplicity and efficiency. The naive trial division is easy to understand but becomes very slow for large ranges. The optimized trial division significantly improves performance by reducing the number of checks to the square root of the number. For very large upper bounds where you need to find many primes, the Sieve of Eratosthenes offers the best performance by pre-calculating all primes up to the limit.

Summary

• Prime Number Definition: A natural number greater than 1 with no positive divisors other than 1 and itself.
• Naive Trial Division: Checks divisibility from 2 up to number - 1. Simple but inefficient.
• Optimized Trial Division: Checks divisibility from 2 (or 3 for odds) up to sqrt(number). More efficient for individual number checks.
• Sieve of Eratosthenes: An algorithm for finding all primes up to a specific limit by marking multiples of primes as composite. Highly efficient for finding many primes in a dense range.
• Practical Considerations: Choose the algorithm based on the expected range size and performance requirements. For large ranges, Sieve is generally preferred.