Python Program to Find if a Number is Prime or Not Prime Using Recursion

Interested in programming and want to excel in it by choosing the short ways. Then, practicing with the available Java Program list is mandatory.

Recursion in Python:

When a function calls itself and loops until it reaches the intended end state, this is referred to as recursion. It is based on the mathematics idea of recursive definitions, which define elements in a set in terms of other members in the set.

Each recursive implementation contains a base case in which the desired state is reached, and a recursive case in which the desired state is not reached and the function enters another recursive phase.

On each step, the behavior in the recursive situation prior to the recursive function call, the internal self-call, is repeated. Recursive structures are beneficial when a larger problem (the base case) can be solved by solving repeated subproblems (the recursive case) that incrementally advance the program to the base case.
It behaves similarly to for and while loops, with the exception that recursion moves closer to the desired condition, whereas for loops run a defined number of times and while loops run until the condition is no longer met.

In other words, recursion is declarative because you specify the desired state, whereas for/while loops are iterative because you provide the number of repeats.

Examples:

Example1:

Input:

given number  = 97

Output:

The given number 97 is prime number.

Example2:

Input:

given number  = 139

Output:

The given number 139 is a prime number.

Program to Find if a Number is Prime or Not Prime Using Recursion in Python

Using recursion, the program takes a number and determines whether or not it is prime.

If a number is only divided by itself and one, it is said to be prime.

So we iterate from 2 to n-1, returning False if n is divisible by any of (2,3,4,…n-1).

In addition, we look for other factors or divisors of the number, and if the remainder is zero, we know the number has factors and is not prime.

Also, if j==n, then there is no number from (2,3,4,…n-1) that is divisible by n, implying that it is prime.

Below are the ways to Find if a Number is Prime or Not Prime using the recursive approach in Python:

Using Recursion(Static Input)
Using Recursion(User Input)

1)Using Recursion(Static Input)

Approach:

Give the number as static input and store it in a variable.
Pass the number to a recursive function as an argument, and set the divisor count to NULL.
The number’s divisors are then checked via recursion, and either True or False is returned.
If the function returns true then it is a prime number.
Else it is not a prime number.
The exit of the program.

Below is the implementation:

def checkPrimeRecursion(numb, divisors=None):
    if divisors is None:
        divisors = numb - 1
    while divisors >= 2:
        if numb % divisors == 0:
            # if we find the divisor then return false because it is not prime
            return False
        else:
            return checkPrimeRecursion(numb, divisors-1)
    else:
      # if we reach here return true because we did not find any
      # divisors of the given number
        return True


# Give the number as static input and store it in a variable.
given_numb = 97
# passing the given number as argument to the recursive function checkPrimeRecursion.
# If the function returns true then it is a prime number.
if(checkPrimeRecursion(given_numb)):
    print('The given number', given_numb, 'is a prime number.')
# Else it is not a prime number.
else:
    print('The given number', given_numb, 'is not a prime number.')

Output:

The given number 97 is prime number.

2)Using Recursion(User Input)

Approach:

Give the number as user input using the int(input()) function and store it in a variable.
Pass the number to a recursive function as an argument, and set the divisor count to NULL.
The number’s divisors are then checked via recursion, and either True or False is returned.
If the function returns true then it is a prime number.
Else it is not a prime number.
The exit of the program.

Below is the implementation:

def checkPrimeRecursion(numb, divisors=None):
    if divisors is None:
        divisors = numb - 1
    while divisors >= 2:
        if numb % divisors == 0:
            # if we find the divisor then return false because it is not prime
            return False
        else:
            return checkPrimeRecursion(numb, divisors-1)
    else:
      # if we reach here return true because we did not find any
      # divisors of the given number
        return True


# Give the number as user input using the int(input()) function and store it in a variable.
given_numb = int(input('Enter some random number = '))
# passing the given number as argument to the recursive function checkPrimeRecursion.
# If the function returns true then it is a prime number.
if(checkPrimeRecursion(given_numb)):
    print('The given number', given_numb, 'is a prime number.')
# Else it is not a prime number.
else:
    print('The given number', given_numb, 'is not a prime number.')

Output:

Enter some random number = 139
The given number 139 is a prime number.

Related Programs: