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