C++ Program to Print Prime Numbers in a Range

Use a C++ program that takes two numbers as input and checks each number in the range using a loop and a function to test if it is prime, then prints the prime numbers; for example, use for loops and a helper function with if conditions to check divisibility.

Examples

Input2 10

Output2 3 5 7

Input11 20

Output11 13 17 19

Input14 16

Output

How to Think About It

To print prime numbers in a range, start from the lower limit and go up to the upper limit. For each number, check if it is prime by testing if it has any divisor other than 1 and itself. If no divisor is found, print the number as prime.

Algorithm

1

Get the starting and ending numbers of the range.

2

For each number in the range, check if it is prime.

3

To check prime, test divisibility from 2 up to the square root of the number.

4

If no divisor is found, print the number.

5

Repeat until the end of the range.

Code

cpp

#include <iostream>
#include <cmath>
using namespace std;

bool isPrime(int n) {
    if (n <= 1) return false;
    for (int i = 2; i <= sqrt(n); i++) {
        if (n % i == 0) return false;
    }
    return true;
}

int main() {
    int start, end;
    cin >> start >> end;
    for (int num = start; num <= end; num++) {
        if (isPrime(num)) cout << num << " ";
    }
    return 0;
}

Output

2 3 5 7 

Dry Run

Let's trace input 2 10 through the code

1

Input range

start = 2, end = 10

2

Check number 2

2 is prime (no divisors found)

3

Check number 3

3 is prime (no divisors found)

4

Check number 4

4 is not prime (divisible by 2)

5

Check number 5

5 is prime (no divisors found)

6

Check number 6

6 is not prime (divisible by 2)

7

Check number 7

7 is prime (no divisors found)

8

Check number 8

8 is not prime (divisible by 2)

9

Check number 9

9 is not prime (divisible by 3)

10

Check number 10

10 is not prime (divisible by 2)

Number	Is Prime?
2	Yes
3	Yes
4	No
5	Yes
6	No
7	Yes
8	No
9	No
10	No

Why This Works

Step 1: Check divisibility

The function isPrime checks if a number has any divisor other than 1 and itself by testing all numbers from 2 to the square root of the number.

Step 2: Loop through range

The main loop goes through each number in the given range and calls isPrime to decide if it should be printed.

Step 3: Print prime numbers

Only numbers confirmed as prime by isPrime are printed, separated by spaces.

Alternative Approaches

Sieve of Eratosthenes

cpp

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int start, end;
    cin >> start >> end;
    vector<bool> prime(end+1, true);
    prime[0] = prime[1] = false;
    for (int i = 2; i*i <= end; i++) {
        if (prime[i]) {
            for (int j = i*i; j <= end; j += i) {
                prime[j] = false;
            }
        }
    }
    for (int i = start; i <= end; i++) {
        if (prime[i]) cout << i << " ";
    }
    return 0;
}

This method is faster for large ranges but uses extra memory to store primes.

Check divisibility up to n/2

cpp

#include <iostream>
using namespace std;

bool isPrime(int n) {
    if (n <= 1) return false;
    for (int i = 2; i <= n/2; i++) {
        if (n % i == 0) return false;
    }
    return true;
}

int main() {
    int start, end;
    cin >> start >> end;
    for (int num = start; num <= end; num++) {
        if (isPrime(num)) cout << num << " ";
    }
    return 0;
}

Simpler but slower than checking up to square root, less efficient for large numbers.

Complexity: O(n * sqrt(m)) time, O(1) space

Time Complexity

For each number in the range (n), we check divisibility up to its square root (sqrt(m)), so total time is O(n * sqrt(m)).

Space Complexity

The program uses constant extra space, only a few variables, so O(1).

Which Approach is Fastest?

The Sieve of Eratosthenes is faster for large ranges but uses O(n) space, while the simple check uses less memory but is slower.

Approach	Time	Space	Best For
Simple check up to sqrt(n)	O(n * sqrt(m))	O(1)	Small to medium ranges
Sieve of Eratosthenes	O(n log log n)	O(n)	Large ranges with many primes
Check up to n/2	O(n * n)	O(1)	Very small ranges or learning purpose