C++ Program to Display Prime Numbers between Given Interval

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.

Page contents:

1. Algorithm

2. Pseudocode

3. Time complexity

4. Program & output

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