C++ Program To Find Prime Numbers In A Given Range

Prime numbers, integers greater than 1 divisible only by 1 and themselves, are fundamental in number theory and have widespread applications in computer science, cryptography, and various mathematical fields. In this article, you will learn how to write C++ programs to efficiently identify and list all prime numbers within a specified numerical range.

Problem Statement

The core problem is to develop C++ code that can determine if a given number is prime and then apply this logic to find all prime numbers within an inclusive range [L, R], where L is the lower bound and R is the upper bound. This task requires careful consideration of computational efficiency, especially for larger ranges.

Example

Given the range [10, 30], the program should output the following prime numbers:

11 13 17 19 23 29

Background & Knowledge Prerequisites

To effectively understand and implement the solutions discussed, readers should be familiar with:

• C++ Basics: Fundamental syntax, data types, and input/output operations.
• Control Flow: Use of for and while loops for iteration, and if-else statements for conditional logic.
• Functions: Defining and calling functions to modularize code.
• Arrays/Vectors: Understanding how to declare and manipulate dynamic arrays for algorithms like the Sieve of Eratosthenes.
• Prime Number Definition: A natural number greater than 1 that has no positive divisors other than 1 and itself. Note that 0 and 1 are not considered prime numbers.

Use Cases or Case Studies

Finding prime numbers within a range has several practical applications:

• Cryptography: Many public-key encryption algorithms, like RSA, rely on the difficulty of factoring large numbers into their prime components. Generating large prime numbers is a crucial step.
• Hash Function Design: Prime numbers are often used in the construction of hash functions to minimize collisions and ensure a uniform distribution of data.
• Random Number Generation: Some pseudo-random number generators incorporate prime numbers or properties related to primality to enhance the randomness and period length of the generated sequences.
• Educational Tools: Developing programs to find primes serves as an excellent exercise for understanding algorithms, optimization techniques, and basic number theory concepts.
• Performance Benchmarking: Different prime-finding algorithms can be used to benchmark CPU performance and test algorithmic efficiency.

Solution Approaches

We will explore three distinct approaches to find prime numbers within a given range, progressing from a straightforward but less efficient method to more optimized ones.

Approach 1: Naive Trial Division

This approach checks each number n in the given range for primality by attempting to divide it by every integer from 2 up to n-1.

• Summary: For each number in the range, iterate from 2 up to the number minus one. If any division results in a zero remainder, the number is not prime.

// Naive Prime Finder in Range
#include <iostream>

// Function to check if a single number is prime using naive trial division
bool isPrimeNaive(int n) {
    if (n <= 1) { // Numbers less than or equal to 1 are not prime
        return false;
    }
    for (int i = 2; i < n; ++i) { // Try dividing by numbers from 2 up to n-1
        if (n % i == 0) { // If divisible, it's not prime
            return false;
        }
    }
    return true; // If no divisors found, it's prime
}

int main() {
    // Step 1: Define the range
    int lowerBound = 10;
    int upperBound = 30;

    std::cout << "Prime numbers in range [" << lowerBound << ", " << upperBound << "] (Naive):" << std::endl;

    // Step 2: Iterate through each number in the range
    for (int i = lowerBound; i <= upperBound; ++i) {
        // Step 3: Check if the current number is prime using the naive function
        if (isPrimeNaive(i)) {
            std::cout << i << " "; // Print if it's prime
        }
    }
    std::cout << std::endl;

    return 0;
}

Run

Sample Output:

Prime numbers in range [10, 30] (Naive):
11 13 17 19 23 29

Stepwise Explanation:

1. isPrimeNaive(int n) function:
   • Handles base cases: numbers n <= 1 are immediately returned as non-prime.

1. main() function:
   • Sets lowerBound and upperBound for the desired range.

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

This is an optimization of the trial division method. Instead of checking divisors up to n-1, we only need to check up to the square root of n. This is because if n has a divisor d > sqrt(n), then it must also have a divisor n/d < sqrt(n).

• Summary: For each number n in the range, check for divisibility only by integers from 2 up to sqrt(n).

// Optimized Prime Finder in Range
#include <iostream>
#include <cmath> // Required for sqrt() function

// Function to check if a single number is prime using optimized trial division
bool isPrimeOptimized(int n) {
    if (n <= 1) { // Numbers less than or equal to 1 are not prime
        return false;
    }
    if (n <= 3) { // 2 and 3 are prime
        return true;
    }
    if (n % 2 == 0 || n % 3 == 0) { // Eliminate multiples of 2 and 3 quickly
        return false;
    }
    // Check for divisors from 5 onwards, skipping multiples of 2 and 3
    // All primes greater than 3 can be expressed in the form 6k +/- 1
    for (int i = 5; i * i <= n; i = i + 6) {
        if (n % i == 0 || n % (i + 2) == 0) {
            return false;
        }
    }
    return true; // If no divisors found, it's prime
}

int main() {
    // Step 1: Define the range
    int lowerBound = 10;
    int upperBound = 30;

    std::cout << "Prime numbers in range [" << lowerBound << ", " << upperBound << "] (Optimized):" << std::endl;

    // Step 2: Iterate through each number in the range
    for (int i = lowerBound; i <= upperBound; ++i) {
        // Step 3: Check if the current number is prime using the optimized function
        if (isPrimeOptimized(i)) {
            std::cout << i << " "; // Print if it's prime
        }
    }
    std::cout << std::endl;

    return 0;
}

Run

Sample Output:

Prime numbers in range [10, 30] (Optimized):
11 13 17 19 23 29

Stepwise Explanation:

1. isPrimeOptimized(int n) function:
   • Handles base cases n <= 1 (non-prime) and n <= 3 (prime).

1. main() function:
   • Identical to the naive approach, but calls isPrimeOptimized(i) for primality testing.

Approach 3: Sieve of Eratosthenes

The Sieve of Eratosthenes is an efficient algorithm for finding all prime numbers up to a specified integer N. It works by iteratively marking as composite (i.e., not prime) the multiples of each prime, starting with 2.

• Summary: Create a boolean array isPrime up to the upper bound R, initialized to true. Mark 0 and 1 as non-prime. Then, starting from p = 2, if p is prime, mark all its multiples (2p, 3p, 4p, ...) as non-prime. Repeat this for all numbers up to sqrt(R). Finally, iterate through the isPrime array in the given range [L, R] to print the primes.

// Sieve of Eratosthenes Prime Finder
#include <iostream>
#include <vector> // Required for std::vector

// Function to implement the Sieve of Eratosthenes
void sieveOfEratosthenes(int upperBound, std::vector<bool>& isPrime) {
    // Step 1: Initialize all entries as true. A value in isPrime[i] will be false if i is not prime, else true.
    isPrime.assign(upperBound + 1, true); // Resize and fill with true
    isPrime[0] = false; // 0 is not prime
    isPrime[1] = false; // 1 is not prime

    // Step 2: Start from the first prime number, 2
    for (int p = 2; p * p <= upperBound; ++p) {
        // If isPrime[p] is still true, then it is a prime
        if (isPrime[p] == true) {
            // Mark all multiples of p as not prime
            // Start from p*p because smaller multiples (p*2, p*3, etc.) would have already been marked
            // by smaller prime factors (2, 3, etc.)
            for (int i = p * p; i <= upperBound; i += p)
                isPrime[i] = false;
        }
    }
}

int main() {
    // Step 1: Define the range
    int lowerBound = 10;
    int upperBound = 30;

    // Step 2: Declare a boolean vector to store primality information
    // Its size will be upperBound + 1 to accommodate numbers from 0 to upperBound
    std::vector<bool> isPrime;

    // Step 3: Run the Sieve to populate the isPrime vector up to upperBound
    sieveOfEratosthenes(upperBound, isPrime);

    std::cout << "Prime numbers in range [" << lowerBound << ", " << upperBound << "] (Sieve):" << std::endl;

    // Step 4: Iterate through the specified range and print primes based on the Sieve result
    // Ensure lowerBound is at least 0. If it's less, adjust to 0 for vector access.
    int start = (lowerBound < 0) ? 0 : lowerBound;
    if (start > upperBound) {
        std::cout << "Invalid range." << std::endl;
        return 0;
    }

    for (int i = start; i <= upperBound; ++i) {
        if (isPrime[i]) {
            std::cout << i << " ";
        }
    }
    std::cout << std::endl;

    return 0;
}

Run

Sample Output:

Prime numbers in range [10, 30] (Sieve):
11 13 17 19 23 29

Stepwise Explanation:

1. sieveOfEratosthenes(int upperBound, std::vector& isPrime) function:
   • Initializes a std::vector named isPrime of size upperBound + 1, setting all values to true. This array will store whether an index i is prime (true) or not (false).

1. main() function:
   • Defines lowerBound and upperBound.

Conclusion

We've explored three methods for finding prime numbers within a given range in C++. The naive trial division, while simple to understand, is inefficient for larger numbers. The optimized trial division significantly improves performance by checking divisors only up to the square root of the number and further by skipping multiples of 2 and 3. For finding all primes up to a specific limit, the Sieve of Eratosthenes is the most efficient, pre-calculating primality for an entire range.

Summary

• Naive Trial Division: Checks divisibility from 2 up to n-1. Simple but slow, O(n) per number, O(N*R) for a range [L, R].
• Optimized Trial Division: Checks divisibility from 2 up to sqrt(n). Faster, O(sqrt(n)) per number, O(sqrt(R)*R) for a range [L, R]. Includes quick checks for 2 and 3 and a 6k +/- 1 optimization.
• Sieve of Eratosthenes: Pre-computes all primes up to an upper bound R efficiently. O(R log log R) for the entire sieve creation, then O(R) to iterate and print. Best for larger ranges or when primality for many numbers up to a limit is needed.
• Understanding the properties of prime numbers and applying algorithmic optimizations can drastically improve program performance for these mathematical tasks.