C++ Program to Display Prime Numbers Between Two Intervals

Prime Numbers are fundamental elements in mathematics and computer science, representing numbers greater than 1 that have no divisors other than 1 and themselves. The task of identifying prime numbers between two intervals highlights key programming concepts such as loops, conditionals, and functions, and is an excellent example of applying computational thinking to solve mathematical problems.

• Understanding the Task

Displaying prime numbers between two intervals involves iterating through all the numbers in the specified range and checking each number to determine if it is prime. This task is computationally intensive, especially for large intervals, due to the nature of prime number determination. Hence, optimizing the prime check process is crucial to improving the program’s efficiency.

Optimized Approach to Prime Checking

The standard approach to check if a number is prime involves dividing the number by all smaller numbers up to 2. This method can be optimized by observing that:

1. No prime number is divisible by any number greater than its square root.
2. Numbers less than 2 are not prime.

Based on these observations, the prime checking function can significantly reduce the number of iterations, enhancing performance.

Implementing the Program

The program will consist of two parts:

1. A function to check if a number is prime.
2. The main function that iterates through the range, uses the prime-checking function, and displays the primes.

C++ Program to Display Prime Numbers Between Two Intervals

#include <iostream>

#include <cmath> // For the sqrt() function

using namespace std;

// Function to check if a number is prime

bool isPrime(int num) {

    if (num < 2) return false; // Numbers less than 2 are not prime

    for (int i = 2; i <= sqrt(num); ++i) {

        if (num % i == 0) return false; // If divisible, not prime

    }

    return true; // Number is prime

}

int main() {

    int start, end;

    // Prompt the user for the interval

    cout << “Enter two numbers (intervals): “;

    cin >> start >> end;

    cout << “Prime numbers between ” << start << ” and ” << end << ” are: ” << endl;

    // Iterate through the range and display prime numbers

    for (int num = start; num <= end; ++num) {

        if (isPrime(num)) {

            cout << num << ” “;

        }

    }

    return 0;

}

Program Explanation

• Prime Checking Function (isPrime):

This function takes an integer as input and returns true if the number is prime, otherwise false. It efficiently checks divisibility only up to the square root of the number, leveraging the mathematical insight that factors of a number are always found in pairs, one less than and one greater than the square root of the number.

• Main Function:

The main function begins by asking the user to input two numbers, defining the interval within which to find prime numbers. It then iterates through each number in this interval, using the isPrime function to check for primality. Prime numbers are displayed to the user.

• Efficiency and Optimization:

The program is optimized for efficiency by reducing the number of divisions needed to determine if a number is prime. This is critical for larger numbers and wider ranges, where naive approaches might lead to significantly longer computation times.