C Program To Find Prime Numbers In Given Range Using Functions

Finding prime numbers within a specified range is a fundamental task in number theory and programming. In this article, you will learn how to write a C program that efficiently identifies all prime numbers between two given integers by using functions.

Problem Statement

The challenge is to identify and list all integers that are prime within a user-defined lower and upper bound. A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself. For instance, in the range of 10 to 20, the prime numbers are 11, 13, 17, and 19. The solution must be structured using C functions for modularity and readability.

Example

Given an input range from 10 to 30, the expected output would be:

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

Background & Knowledge Prerequisites

To understand this article, you should have a basic grasp of:

• C Programming Basics: Variables, data types, input/output operations.
• Control Flow Statements: for loops, if-else statements.
• Functions: Declaring, defining, and calling functions in C.

Use Cases or Case Studies

Identifying prime numbers has several practical applications across various domains:

• Cryptography: Prime numbers are essential for public-key cryptographic systems like RSA, where the security relies on the difficulty of factoring large numbers into their prime components.
• Number Theory Research: Many mathematical conjectures and theorems in number theory are based on the properties and distribution of prime numbers.
• Educational Tools: Programs that find prime numbers serve as excellent exercises for teaching fundamental programming concepts, algorithm design, and optimization techniques.
• Algorithm Benchmarking: The efficiency of prime-finding algorithms can be used to benchmark processor performance or test different language implementations.
• Hashing Functions: Prime numbers are sometimes used in the design of hash functions to minimize collisions and ensure a more even distribution of data.

Solution Approaches

We will focus on a trial division method, which is straightforward to implement using a helper function. We will also look at a common optimization for this method.

Approach 1: Basic Primality Test Function

This approach involves creating a separate function to check if a single number is prime. The main function then iterates through the given range, calling this helper function for each number.

One-line summary

Iterate through the range and use a isPrime() helper function to determine if each number is prime by checking divisibility up to itself.

Code example

// Find Primes in Range using Basic Function
#include <stdio.h>
#include <stdbool.h> // For using bool data type

// Function to check if a number is prime
bool isPrime(int num) {
    if (num <= 1) {
        return false; // Numbers less than or equal to 1 are not prime
    }
    // Check for divisibility from 2 up to num-1
    for (int i = 2; i < num; i++) {
        if (num % i == 0) {
            return false; // If divisible, it's not prime
        }
    }
    return true; // If no divisors found, it's prime
}

int main() {
    // Step 1: Declare variables for the range
    int lowerBound, upperBound;

    // Step 2: Get input for the range from the user
    printf("Enter the lower bound of the range: ");
    scanf("%d", &lowerBound);
    printf("Enter the upper bound of the range: ");
    scanf("%d", &upperBound);

    // Step 3: Ensure valid range (lower <= upper)
    if (lowerBound > upperBound) {
        int temp = lowerBound;
        lowerBound = upperBound;
        upperBound = temp;
    }

    // Step 4: Print a header for the output
    printf("Prime numbers between %d and %d are:\\n", lowerBound, upperBound);

    // Step 5: Iterate through the range and check each number for primality
    for (int i = lowerBound; i <= upperBound; i++) {
        if (isPrime(i)) {
            printf("%d ", i);
        }
    }
    printf("\\n"); // Newline for better formatting

    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. isPrime Function Definition:

• The isPrime(int num) function takes an integer num as input and returns a boolean value (true if prime, false otherwise).
• It first handles edge cases: numbers less than or equal to 1 are not prime, so it immediately returns false.
• A for loop then iterates from i = 2 up to num - 1.
• Inside the loop, num % i == 0 checks if num is divisible by i. If it is, num has a divisor other than 1 and itself, so it's not prime, and the function returns false.
• If the loop completes without finding any divisors, it means num is prime, and the function returns true.

1. main Function Flow:

• Variables lowerBound and upperBound are declared to store the user-defined range.
• The program prompts the user to enter these bounds using printf and reads them using scanf.
• A check if (lowerBound > upperBound) ensures that the lowerBound is always less than or equal to the upperBound by swapping them if necessary.
• A for loop iterates from lowerBound to upperBound.
• In each iteration, the isPrime(i) function is called.
• If isPrime(i) returns true, the number i is printed as a prime number.
• Finally, a newline character is printed for clean output.

Approach 2: Optimized Primality Test (Checking Divisors up to Square Root)

The previous isPrime function checks for divisors up to num - 1. This can be optimized because if a number n has a divisor d greater than sqrt(n), then it must also have a divisor n/d which is less than sqrt(n). Therefore, we only need to check for divisors up to the square root of num.

One-line summary

Improve the isPrime() function by checking for divisors only up to the square root of the number, significantly reducing computations.

Code example

// Find Primes in Range using Optimized Function
#include <stdio.h>
#include <stdbool.h> // For using bool data type
#include <math.h>    // For using sqrt() function

// Function to check if a number is prime (optimized)
bool isPrime(int num) {
    if (num <= 1) {
        return false; // Numbers less than or equal to 1 are not prime
    }
    if (num <= 3) {
        return true;  // 2 and 3 are prime
    }
    if (num % 2 == 0 || num % 3 == 0) {
        return false; // Multiples of 2 or 3 are not prime
    }

    // Check for divisibility from 5 onwards
    // Optimized: only check up to sqrt(num)
    // and only check numbers of the form 6k ± 1
    for (int i = 5; i * i <= num; i = i + 6) {
        if (num % i == 0 || num % (i + 2) == 0) {
            return false; // If divisible, it's not prime
        }
    }
    return true; // If no divisors found, it's prime
}

int main() {
    // Step 1: Declare variables for the range
    int lowerBound, upperBound;

    // Step 2: Get input for the range from the user
    printf("Enter the lower bound of the range: ");
    scanf("%d", &lowerBound);
    printf("Enter the upper bound of the range: ");
    scanf("%d", &upperBound);

    // Step 3: Ensure valid range (lower <= upper)
    if (lowerBound > upperBound) {
        int temp = lowerBound;
        lowerBound = upperBound;
        upperBound = temp;
    }

    // Step 4: Print a header for the output
    printf("Prime numbers between %d and %d are:\\n", lowerBound, upperBound);

    // Step 5: Iterate through the range and check each number for primality
    for (int i = lowerBound; i <= upperBound; i++) {
        if (isPrime(i)) {
            printf("%d ", i);
        }
    }
    printf("\\n"); // Newline for better formatting

    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. isPrime Function Definition (Optimized):

• Includes math.h for sqrt() (though the loop i * i <= num avoids explicitly calling sqrt in each iteration, which is slightly more efficient).
• Handles edge cases for num <= 1 (not prime).
• Quickly returns true for num = 2 and num = 3.
• Quickly returns false for even numbers (except 2) and multiples of 3 (except 3).
• The for loop for checking divisors starts from i = 5. It iterates only up to i * i <= num (equivalent to i <= sqrt(num)).
• The increment i = i + 6 is a further optimization: all primes greater than 3 can be expressed in the form 6k ± 1. This loop checks i and i + 2 (which correspond to 6k - 1 and 6k + 1 forms) in each step, skipping multiples of 2 and 3 efficiently.
• If num is divisible by i or i + 2, it's not prime, and the function returns false.
• If the loop completes without finding divisors, num is prime, and the function returns true.

1. main Function Flow:

• The main function remains identical to the basic approach. The only change is that it now calls the optimized isPrime function, which performs the primality test much more efficiently, especially for larger numbers.

Conclusion

Using functions to modularize code is a best practice, making programs more readable, maintainable, and reusable. We successfully implemented a C program to find prime numbers within a given range using a dedicated isPrime function. Furthermore, we explored an optimization technique that significantly improves the performance of the primality test by checking divisors only up to the square root of the number, demonstrating how algorithmic enhancements can lead to more efficient solutions.

Summary

• Prime numbers are integers greater than 1 with only two divisors: 1 and themselves.
• The problem involves listing all primes within a specified lower and upper bound.
• A helper function, isPrime(), encapsulates the logic for checking individual number primality.
• The main function iterates through the range, calling isPrime() for each number.
• An important optimization for isPrime() is to check for divisors only up to the square root of the number.
• Further optimizations can involve handling multiples of 2 and 3 separately and then checking numbers of the form 6k ± 1.
• Modular programming with functions enhances code readability and maintainability.