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

program to find prime numbers in given range

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

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 150+ courses offered by PrepInsta in One Subscription

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;
    }


  • 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;

    }


  • 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;

    }