# C++ Program to Print Prime numbers in a given range

## Program to find Prime Numbers in a given range in C++

Here we will discuss how to find prime numbers in the range specified by the user using C++ programming language.

```Prime numbers are the numbers which have 2 divisors only
i.e. can be divided by 1 & itself

Example: 2, 3, 5, 7, 11, 13 .... etc
```

In this program, the user will specify a range and we will check for every number in the range for being prime ## Methods

We recommend going ahead with the codes on the page – Check if a number is prime or not in C++ before moving ahead with the methods below.

1. Method 0: Check divisors between [2, n-1]
2. Method 1: Check divisors between [2, n/2]
3. Method 2: Check divisors between [2, √n]
4. Method 3: Check divisors between [2, √n]. But, skipping even iterations.

## Method 0

### C++ Code

Run
```#include
using namespace std;

bool isPrime(int n){
int count = 0;

// 0, 1 negative numbers are not prime
if(n < 2)
return false;

// checking the number of divisors b/w 1 and the number n-1
for(int i = 2;i < n; i++)
{
if(n % i == 0)
return false;
}

// if reached here then must be true
return true;
}

int main()
{
int lower, upper;

lower=1,upper=100;

for(int i = lower; i <= upper; i++)
if(isPrime(i))
cout << i << " ";

}
// Time Complexity : O(N^2)
// Space Complexity : O(1)```

### Output

`2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 `

## Method 1

### C++ Code

Run
```#include <iostream>
using namespace std;

bool isPrime(int n){
int count = 0;

// 0, 1 negative numbers are not prime
if(n < 2)
return false;

// checking the number of divisors b/w 1 and the number n
for(int i = 2;i < n/2; i++)
{
if(n % i == 0)
return false;
}

// if reached here then must be true
return true;
}

int main()
{
int lower, upper;

lower=1,upper=100;

for(int i = lower; i <= upper; i++)
if(isPrime(i))
cout << i << " ";

}
// Time Complexity : O(N^2)
// Space Complexity : O(1)
```

### Output

`2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 `

## Method 2

We recommend going ahead with the codes on the page – Check if a number is prime or not in C++ before moving ahead.

### C++ Code

Run
```#include <iostream>
#include <math.h>

using namespace std;

bool isPrime(int n){
int count = 0;

// 0, 1 negative numbers are not prime
if(n < 2)
return false;

// A number n is not a prime, if it can be factored into two factors a & b:
// n = a * b

/*Now a and b can't be both greater than the square root of n, since
then the product a * b would be greater than sqrt(n) * sqrt(n) = n.
So in any factorization of n, at least one of the factors must be
smaller than the square root of n, and if we can't find any factors
less than or equal to the square root, n must be a prime.
*/
for(int i = 2;i < sqrt(n); i++)
{
if(n % i == 0)
return false;
}

// if reached here then must be true
return true;
}

int main()
{
int lower, upper;

lower=1,upper=100;

for(int i = lower; i <= upper; i++)
if(isPrime(i))
cout << i << " ";

}
// Time Complexity : O(N√N)
// Space Complexity : O(1)
```

### Output

`Enter lower and upper ranges : 20 5023 25 29 31 37 41 43 47 49 `

## Method 3

We recommend going ahead with the codes on the page – Check if a number is prime or not in C++ before moving ahead.

### C++ Code

Run
```#include <iostream>
#include <math.h>

using namespace std;

bool isPrime(int n){
// 0 and 1 are not prime numbers
// negative numbers are not prime
if (n <= 1)
return false;

// special case as 2 is the only even number that is prime
else if (n == 2)
return true;

// Check if n is a multiple of 2 thus all these won't be prime
else if (n % 2 == 0)
return false;

// If not, then just check the odds
for (int i = 3; i <= sqrt(n); i += 2)
{
if (n % i == 0)
return false;
}

return true;
}

int main()
{
int lower, upper;

lower=1,upper=100;

for(int i = lower; i <= upper; i++)
if(isPrime(i))
cout << i << " ";

}
// Time Complexity : O(N^2)
// Space Complexity : O(1)```

### Output

`2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97`

## Other website’s Code

Some other websites have also given the following codes, which more as less give the same time complexity. But, are for no reason complex in code logic. We have still added them below so you can see all methods of prime numbers.

### Other website Method 1

Run
```#include <iostream>
using namespace std;

int main ()
{
int lower=1, upper=100;

for (int i = lower; i < upper; i++){
if(i == 2){
cout << i << " ";
continue;
}
for (int j = 2; j < i; j++)
{
// if current i is divisible by any j
// i is not prime
if (i % j == 0)
break;
// if j reached i - 1
// we checked all numbers b/w [2, i-1] none are divisors
// thus number must be prime
else if (i == j+1)
cout << i << " ";

}
}
return 0;
}```

#### Output

` 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 7`

### Other website Method 2

Below is complex for no reason. the explanation of this code is given later after the code below –
```#include
using namespace std;

int main () {
int lower, upper;
int i, j;

cout << "Enter lower and upper ranges : ";
cin >> lower >> upper;

// Note : Explanation for this code given below in another code
for(i = lower; i<upper; i++) {
if(i < 2)
continue;

for(j = 2; j <= (i/j); j++)
if(!(i%j))
break;```
// if factor found, not prime if(j > (i/j)) cout << i << ” “; } return 0; }

#### Output

``` Enter lower and upper ranges : 1 100
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97```

### Other website Method 2 (Explanation)

```// This code is confusing and not ideal to code
// due its complex coding nature, what we have dicussed in previous
// methods is better and has same time complexity
#include<iostream>
using namespace std;

int main () {
int lower, upper;
int i, j;

cout << "Enter lower and upper ranges : ";     cin >> lower >> upper;

for(i = lower; i <= upper; i++) {
if(i < 2)
continue;
// why j <= (i/j)?
// Basically its same as j <= sqrt(i), which is
// critical boundary condition to check for prime number
// we can write j <= (i/j) as -> j * j <= i (multiplying by j on both sides)
// now apply sqrt on both sides it will become j <= sqrt(i)
for(j = 2; j <= (i/j); j++)         {             // why this ?             // its same as writing (i % j) == 0, we are just using not operator             if(!(i % j))                 break;// if factor found, not prime         }         // why this?         // basically we are checking if sqrt(i) has become greater than i         // which would mean we have checked all numbers b/w 2 to sqrt(i)         // and found no divisors and thus it must be prime         if(j > (i/j))
cout << i << " ";
}

return 0;
}```

#### Output

``` Enter lower and upper ranges : 1 100
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97```

### Related Banners

Get PrepInsta Prime & get Access to all 150+ courses offered by PrepInsta in One Subscription

### 3 comments on “C++ Program to Print Prime numbers in a given range”

• #include

using namespace std;

int main()
{
int n;
cin>>n;
for(int i=2;i<=n;i++){
int j;
for( j=2;j<i;j++){
if(i%j==0){
break;
}
}
if(j==i){
cout<<i<<endl;
}
}

return 0;
} 0
• Y.PRAVEEN

#include
using namespace std;

int main ()
{

int n, i, c = 0, count = 0;

for (n = 1; n <= 10; n++)
{
for (i = 1; i <=n; i++)
{
if (n % i == 0)

c++;
}

if(c==2)
{ count++;
//printf(" %d ",n);
cout<<" "<<n<=2)
c = 0;

}

printf (“The no of prime numbers = %d\n”, count);

return 0;

} 0
• Y.PRAVEEN

easy method
#include
using namespace std;

int main ()
{

int n, i, c = 0, count = 0;

for (n = 1; n <= 10; n++)
{
for (i = 1; i <=n; i++)
{
if (n % i == 0)

c++;
}

if(c==2)
{ count++;
//printf(" %d ",n);
cout<<" "<<n<=2)
c = 0;

}

printf (“The no of prime numbers = %d\n”, count);

return 0;

} 0