Prime Number Program in C++

June 29, 2023

C++ Program to Check Whether the Number is Prime or Not

A prime number is a number that can be divided by 1 and itself i.e. a number that can not be divided by any other number other than 1 or itself is a prime number.

Example 
Input : 5
Output : 5 is a Prime

Check Whether the Number is a Prime or Not in C++

The objective of the above problem statement is to write a C++ program to check whether or not the given integer input is a Prime number or not. To do so we’ll check if the number is divisible by 2, if so it’s not a prime. Similarly, we’ll keep dividing the number input with all the numbers until square root of the number input, if divisible with any of those, it’s not a Prime. Here are some of the methods mentioned below to solve the above mentioned problem

Method 1: Simple iterative solution
Method 2: Optimization by break condition
Method 3: Optimization by n/2 iterations
Method 4: Optimization by √n
Method 5: Optimization by skipping even iteration
Method 6: Basic Recursion technique

We’ll discuss the above mentioned methods in detail in the sections below.

Method 1: Simple iterative solution

Any prime number would not be divisible by more than 2 numbers (1 and itself). We run a loop between [1, n] and check if number of divisors of n are greater than 2 or not.

C++ Code

Run

#include<iostream>
using namespace std;

int main()
{
    int a = 0, count = 0;
    int n = 21;
    
    // checking the number of divisors b/w 1 and the number n
    for(int i=1;i < n+1; i++) { if(n % i == 0) count += 1; } //if the number of divisors are > 2 then its not prime else its prime 
// 0 and 1 are not prime numbers 
if (n == 0 || n == 1) {
cout << "The given is number " << n <<" is not prime";} else if(count > 2)
    { cout<<"The given number " << n <<" is not prime";} 
else 
    {cout<<"The given number " << n <<" is prime";}
return 0;
 } 
// Time Complexity : O(N) 
// Space Complexity : O(1)

Output

The given number 21 is not prime

Method 2: Optimization by break condition

This method works on the following observation –

Any prime number n would not be divisible in the range [2, n-1]
1, 0 and negative numbers are not prime

C++ Code

Run

#include<iostream>

using namespace std;

int main()
{
    int i,n = 13;
    bool isprime= true;
    
    // 0 and 1 are not prime numbers also, negative numbers are not prime
    if(n < 2)
    {
        isprime = false;
    }
    else
    {
        for(i=2;i < n;i++)
        {
            if(n % i == 0)
            {
                isprime = false;
                break;
            }
        }
    }

    string result = isprime ? "Prime" : "not Prime";
    cout<<"The number " << n << " is : " << result;
    
    return 0;
}
// Time Complexity : O(N)
// Space Complexity : O(1)
// This program is better than previous version as :
// Condition for 0, 1 and negative numbers checked earlier
// Loops runs b/w [2, n-1] rather than [1, n]

Output

The number 13 is : Prime

Method 3: Optimization by n/2 iterations

This method works on the following observation –

Any Prime number doesn’t have any divisors in range [n/2+1, n-1]
- Example – 33 won’t have any divisors in range [19, 32]

C++ Code

Run

#include<iostream>

using namespace std;

int main()
{
    int i,n = 33;
    bool isprime= true;
    
    // 0 and 1 are not prime numbers also, negative numbers are not prime
    if(n < 2)
    {
        isprime = false;
    }
    else
    {
    // running loop till n is wasteful because for any number n the numbers in
    // the range(n/2 + 1, n) won't be divisible anyways.
        for(i=2; i < n/2; i++)
        {
            if(n % i == 0)
            {
                isprime = false;
                break;
            }
        }
    }

    string result = isprime ? "Prime":"not Prime";
    cout<<"The number " << n << " is : " << result;
    
    return 0;
}
// Time Complexity : O(N)
// Space Complexity : O(1)
// This program is better than previous version as :
// Loops runs b/w [2, n/2] rather than [2, n-1]

Output

The number 33 is : Prime

Method 4: Optimization by √n

This method works on the following observation –

We can check for prime numbers by running iterative loop only b/w [2, sqrt(n)]

Detailed explanation given in the code

C++ Code

Run

#include<iostream>
#include<math.h>
using namespace std;

int main()
{
    int i,n = 29;
    bool isprime= true;
    
    // 0 and 1 are not prime numbers also, negative numbers are not prime
    if(n < 2)
    {
        isprime = false;
    }
    else
    {
    // If a number n is not a prime, it can be factored into two factors a and 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(i=2; i < sqrt(n); i++)
        {
            if(n % i == 0)
            {
                isprime = false;
                break;
            }
        }
    }

    string result = isprime ? "Prime":"not Prime";
    cout<<"The number " << n << " is : " << result;
    
    return 0;
}
// Time Complexity : O(√N)
// Space Complexity : O(1)
// This program is better than previous version as :
// Loops runs b/w [2, √n] rather than [2, n/2]

Output

The number 29 is : Prime

Method 5: Optimization by skipping even iteration

This method works on the following observation –

2 is the only even prime number
We can skip all even iterations if we check for divisibility with 2 earlier than iterative loop

C++ Code

Run

#include<bits/stdc++.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 n = 29;
    
    if (isPrime(n))
        cout << n << " is a Prime Number";
    else
        cout << n << " is not a Prime Number";

    return 0;
}
//Time complexity : O(√N)
//Space complexity : O(1)
//This code is better than previous code
//We skipping all even iterations b/w [3, √num]

Output

The number 29 is : Prime

Method 6: Basic Recursion technique

In this method we’ll use the knowledge of recursion in C++ to solve the above mentioned problem.

C++ Code

Run

#include<iostream>
using namespace std;

bool checkPrime(int n, int i)
{
    // 0, 1 and negative numbers are not prime
    if (n < 2)
        return false;

    // if this satisfies then its prime as we
    // have completed recursion from 2 to n
    if (i == n)
        return true;

    // Base cases
    if (n % i == 0)
        return false;

    i += 1;
    return checkPrime(n, i);
}

int main()
{
    int i = 2;
    bool isprime= true;
    
    int n = 37;
    isprime=checkPrime(n, i);
    
    string result = isprime ? "Prime":"not Prime";
    cout<< n << " is : "<< result;
    
    return 0;
}
// Time Complexity : O(N)
// Space Complexity : O(1)
// Auxillary Space complexity : O(N)
// Due to function call stack

Output

The number 37 is : Prime

Greatest of the Three numbers

Leap year or not

Prime number within a given range

Sum of digits of a number

Reverse of a number

Prime Course Trailer

Related Banners

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

Getting Started

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
Finding Prime Factors 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

2 comments on “Prime Number Program in C++”

Kunal Krishna
In the optimization by sqrt(n) for checking prime,the condition for(i=2; i < sqrt(n); i++) should be for(i=2; i <= sqrt(n); i++). Otherwise the desired output is not obtained at squares of prime numbers ,for eg: 4,9,25 etc

Log in to Reply
Viji
//prime or not
#include
using namespace std;

int main()
{

int i,n,num;
cout<>n;
for(i=1;i<=n/2;i++)
{
num+=i;
}
if(num%2!=0)
cout<<"prime number ";
else
cout<<"not prime number ";

return 0;
}

Log in to Reply

Unlock this article for Free,
by logging in

Prime Number Program in C++

C++ Program to Check Whether the Number is Prime or Not

Check Whether the Number is a Prime or Not in C++

Method 1: Simple iterative solution

C++ Code

Output

Method 2: Optimization by break condition

C++ Code

Output

Method 3: Optimization by n/2 iterations

C++ Code

Output

Method 4: Optimization by √n

C++ Code

Output

Method 5: Optimization by skipping even iteration

C++ Code

Output

Method 6: Basic Recursion technique

C++ Code

Output

Prime Course Trailer

Related Banners

Getting Started

2 comments on “Prime Number Program in C++”

30+ Companies are Hiring

Unlock this article for Free, by logging in

Prime Number Program in C++

C++ Program to Check Whether the Number is Prime or Not

Check Whether the Number is a Prime or Not in C++

Method 1: Simple iterative solution

C++ Code

Output

Method 2: Optimization by break condition

C++ Code

Output

Method 3: Optimization by n/2 iterations

C++ Code

Output

Method 4: Optimization by √n

C++ Code

Output

Method 5: Optimization by skipping even iteration

C++ Code

Output

Method 6: Basic Recursion technique

C++ Code

Output

Prime Course Trailer

Related Banners

Getting Started

2 comments on “Prime Number Program in C++”

30+ Companies are Hiring

Unlock this article for Free,
by logging in