Checking for Prime number using recursion

Checking for Prime number using recursion

Given an input number , write a program for Checking for Prime number using recursion .

input:-

23

Output:-

23 is a prime number.

Checking for Prime number using recursion:-

The objective of this  code is to recursively check that a given number is prime or not . So for this we will write a function CheckPrime() that will take two parameter number and i   ( i for checking the factors of the number ).  we initialize the i with  2 . The base case for the function is if number is equal to i then it is a prime number so we will return 1 . otherwise we check that if number is divisible by i then it is not a prime number so return 0  and if not divisible then increase the value of i by 1 and call the CheckPrime() function recursively . For better understanding see the example :-

Code (C ++):-

#include<bits/stdc++.h>
using namespace std;

// recursive function to check number is
// prime or not
int CheckPrime(int n ,int i)
{
    
    if(n==i)
      return 1;
    
    else
    {
        if(n%i==0)
           return 0;
        else
          return CheckPrime(n,i+1);
    }
}
int main()
{
    int n;
    cout<<"Enter a number"<<endl;
    cin>>n;
    if(CheckPrime(n,2)==1)
      cout<<n<<" is a prime number"<<endl;
    else
      cout<<n<<" is not a prime number"<<endl;
    return 0;
}

Output:-

Enter a number
23
23 is a prime number

python code:-

def prime(x,i):
    if x==i:
        return 1
    elif x%i==0:
        return 0
    else:
        return prime(x,i+1)

n=int(input("Enter a number "))
n1=prime(n,2)
if  n1==1:
    print(n,"is a prime number")
else:
    print(n,"is not a prime number")

output:-

Enter a number
11
11 is a prime number

 

Recommended Post:-