In this program, we are going to make a c++ program to check prime numbers using for loop and then we also make this program using recursion.

## How do you find a prime number in a for loop C++?

We will simply start our for loop from 2 to √n (given number), and check if the given number is divisible by them or not.

If a number is divisible by any number between 2 to √n, then the given number “n” is not a prime number. If the given number is not divisible by them, then the given number is a prime number.

Related Posts:

C++ program to print prime numbers

## Prime Number Program in Cpp

#include<iostream>

using namespace std;

bool isPrime(int n){

for(int i=2;i*i<=n;i++){

if(n%i==0)

{

return false;

}

}

return true;

}

int main() {

// Write C++ code here

int n;

cin>>n;

if(isPrime(n)){

cout<<n<<" is a Prime Number"<<endl;

}

else

cout<<n<<" is not a Prime Number"<<endl;

return 0;

}

Output: 56

56 is not a Prime Number

56 is not a Prime Number

Time complexity: O(sqrt(n))

## Prime Number Program in C++ using Recursion

In this program, we will check a number whether it is a prime number or not using recursion.

Steps for Recursion:

- Base Case: if i*i is greater than n, then return true.
- Induction step: if n is divisible by i, then return false.

bool isPrime(int n,int i=2){

if(i*i>n)

return true;

if(n%i==0)

return false;

return isPrime(n,i+1);

}

Show Comments