C++ Program to Display Prime Numbers between Given Interval

Prime number

C++ program to display prime numbers between given interval has been shown here. For example, the prime numbers between 1 and 30 are 2, 3, 5, 7, 11, 13, 17, 19, 23, 29. In this program, the upper and lower bounds of the interval are taken as inputs.







1. Algorithm to Display Prime Numbers between Given Interval


1. Take lower bound l and upper bound u as inputs.

2. For each number from l to u, check if it is a prime number.

3. If a number is prime, add it to a list of prime numbers.

4. Display the list after all the numbers within the interval have been checked.




2. Pseudocode to Display Prime Numbers between Given Interval


Input : Lower bound $l$ and Upper bound $u$

Output : Prime numbers between $l$ and $u$

1. Procedure primesBetweenInterval($l, u$):

2. Repeat for $n \in [l, u]$:

3. $flag \leftarrow 0$

4. Repeat for $i \in [2, \sqrt{n}]$:

5. If $n \mod i$ = 0:

6. $flag \leftarrow 1$

7. break

8. If $flag = 0$:

9. Print "$n$ is a prime"

10. End Procedure





3. Time complexity to Display Prime Numbers between Given Interval


Time Complexity: O($n\sqrt{n}$)

Here, $n$ is the number of elements between $l$ and $u$ inclusive




4. C++ Program & output to Display Prime Numbers between Given Interval

Code has been copied
/************************************
    	alphabetacoder.com
C++ program to display prime numbers 
between given interval
*************************************/

#include <iostream>
#include <cmath>

using namespace std;

// function to check prime
int check_prime(int num) {
    // declare variable
    int i;
    // no prime number less than 2, so return false
    if (num < 2)
        return 0;
    // check divisibility of num
    for (i = 2; i <= sqrt(num); i++) {
        if (num % i == 0) {
            return 0; // num is composite so return false
        }
    }
    // num is prime so return true
    return 1;
}

int main() {
    // declare variables
    int n1, n2, i;

    // take input of the inteval
    cout << "Enter the lower and upper bounds of interval = ";
    cin >> n1 >> n2;

    cout << "Prime numbers between " << n1 << " and " << n2 << ": ";
    // find primes between n1 and n2
    for (i = n1; i <= n2; i++) {
        // check if current number is prime
        if (check_prime(i)) {
            cout << i << " ";
        }
    }

    return 0;
}

Output


Enter the lower and upper bounds of interval = 1 30

Prime numbers between 1 and 30: 2 3 5 7 11 13 17 19 23 29