Prime Number Program in Cpp using for loop

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

Related Post:
Palindrome program in c++
Maximum Subarray Sum Kadane Algorithm