Python Program to Check whether a Number is Prime or Not using Recursion

This is a Python Program to find if a number is prime or not using recursion.

Problem Description

The program takes a number and finds if the number is prime or not using recursion.

Problem Solution

1. Take a number from the user.
2. Pass the number as an argument to a recursive function and initialize the divisor count to NULL.
3. Then check the number of divisors of the number using recursion and either True or False is returned.
4. The final result is printed.
5. Exit.

Program/Source Code

Here is source code of the Python Program to find if a number is prime or not using recursion. The program output is also shown below.

def check(n, div = None):
    if div is None:
        div = n - 1
    while div >= 2:
        if n % div == 0:
            print("Number not prime")
            return False
        else:
            return check(n, div-1)
    else:
        print("Number is prime")
        return 'True'
n=int(input("Enter number: "))
check(n)
Program Explanation

1. User must enter a number.
2. The number is passed as an argument to a recursive function and the divisor count is initialized to NULL.
3. The divisor is initialized to the number minus 1.
4. The number of divisors of the number is checked using recursion and either True or False is returned.
5. Final result is printed.

advertisement
advertisement
Runtime Test Cases
 
Case 1:
Enter number: 13
Number is prime
 
Case 2:
Enter number: 30
Number not prime

Sanfoundry Global Education & Learning Series – Python Programs.

To practice all Python programs, here is complete set of 150+ Python Problems and Solutions.

Sanfoundry Certification Contest of the Month is Live. 100+ Subjects. Participate Now!

If you find any mistake above, kindly email to [email protected]

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & discussions at Telegram SanfoundryClasses.