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

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:

1. Base Case: if i*i is greater than n, then return true.
2. 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);}  `