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

September 28, 2022

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.

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

Method 0

Concept used For any number n. We will run a iterative loop between 2 to n-1. If there are divisors of the number in this range, then its not prime

Note : We will straight forward say 0,1 and negative numbers are not prime and handle those in for loop.

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

Concept used For any number n. There would be no divisors in the range [n/2+1, n-1]

Example : For 33, numbers in the range(17, 32) won't divide 33.

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

Leap year

Prime Number

Sum of Digits of a number

Reverse of a number

Palindrome number

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.

Concept used For any number n. We can check of divisors in range [2, sqrt(n)], if we do not find any then its prime number

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 50
23 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.

Concept used 2 is the only even prime number, due to this fact we can skip all even iterations while checking for prime numbers.

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)

The explanation is added as comments

// 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

Prime Course Trailer

Related Banners

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

Positive or Negative number: C | C++ | Java | Python
Even or Odd number: C | C++ | Java | Python
Sum of First N Natural numbers: C | C++ | Java | Python
Sum of N natural numbers: C | C++ | Java | Python
Sum of numbers in a given range: C | C++ | Java | Python
Greatest of two numbers: C | C++ | Java | Python
Greatest of the Three numbers: C | C++ | Java | Python
Leap year or not: C | C++ | Java | Python
Prime number: C | C++ | Java | Python
Prime number within a given range: C | C++ | Java | Python
Sum of digits of a number: C | C++ | Java | Python
Reverse of a number : C | C++ | Java | Python
Palindrome number: C | C++ | Java | Python
Armstrong number : C | C++ | Java | Python
Armstrong number in a given range : C | C++ | Java | Python
Fibonacci Series upto nth term : C | C++ | Java | Python
Find the Nth Term of the Fibonacci Series : C | C++ | Java | Python
Factorial of a number : C | C++ | Java | Python
Power of a number : C | C++ | Java | Python
Factor of a number : C | C++ | Java | Python
Strong number : C | C++ | Java | Python
Perfect number : C | C++ | Java | Python
Automorphic number : C | C++ | Java | Python
Harshad number : C | C++ | Java | Python
Abundant number : C| C++ | Java | Python
Friendly pair : C | C++ | Java | Python

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

aditya pratap
#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;
}

2

Log in to Reply
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

Log in to Reply
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

Log in to Reply