How Do I Find A Prime Number Using Recursion In Python

I have to find out whether number(N) is a prime or not using recursion, no loops are allowed. I've tried converting the usual code that uses a for loop to a recursive one, but it's

Solution 1:

Your solution is close, with just a few changes needed to make it work.

defis_prime(a,N):
    print(a, N)
    if N <= 1:
        returnelse:
        if a >= N:
            print(N)
        else:
            if N == 2: 
                print(N)
            elif (N % a) == 0:
                returnFalseelse:
                return is_prime(a+1,N)

    returnFalse

You didn't give any examples of calling this function, but I assume it's always called with a being 2, since any other value wouldn't make sense. So if you run the above function like so, you should get the right output:

print(is_prime(2, 7))  => Trueprint(is_prime(2, 4))  => Falseprint(is_prime(2, 37)) => True

I think you have a misunderstanding of how recursion works, you're assigning this prime variable in the body of the function, but never doing anything with it. Maybe your confusion comes from a misunderstanding of scopes in Python. That prime variable will not be 'shared' across invocations, it will just create a new prime every time.

EDIT: Didn't realize you wanted the function to just print out the prime if it's a prime, changed the code accordingly.

Solution 2:

Your function sometimes returns something and sometimes returns nothing -- it should be either all one or the other, not both. In this case is_prime() looks like a boolean function so it should return True or False. We'll leave the printing to the caller:

defis_prime(N, a=3):

    if N == 2:  # special case
        prime = Trueelif N <= 1or N % 2 == 0:  # too small or even
        prime = Falseelif a * a > N:  # tried all divisors to sqrt, must be prime
        prime = Trueelif (N % a) == 0:  # divides evenly, not a prime
        prime = Falseelse:  # can't tell yet, recursively try the next (odd) divisor
        prime = is_prime(N, a+2)

    return prime

for x inrange(100):
    if is_prime(x):
        print(x)

Keep it simple. Think through each possible case. Avoid increasing the indention depth unnecessarily, it makes your code more complicated.

The above solution tries to speed up prime detection by avoiding even numbers (both divisor and number) and limiting the divisor to the square root of the number. This can matter as without these optimizations, a recursive solution will likely run out of call stack space at around N=1,000 whereas the above should go to N=1,000,000 without expanding the call stack.

Solution 3:

defprime(n,j):
    if(n<2):
        returnFalseif(j==n):
        returnTrueif(n%j==0):
        returnFalsereturn prime(n,j+1)

print(prime(n,2))

A number is called prime if it is only divisible by itself and 1. So iterate from 2 to n-1, if n is divisible by any of (2,3,4,..n-1) return False. If j == n then there is no such number from (2,3,4...n-1) divisible by n, Hence it's Prime.

Solution 4:

Since the goal is to print the number in case it's prime let's do that part first. You've already got a condition for it in your code but there was no print:

if a >= N:
    print(N)
    return

Next we need to handle all the cases where N > 1:

if N == 2: 
    prime = Trueprint(N)
    returnelif (N % a) == 0:
    prime = Falsereturn is_prime(a+1,N)
else:
    prime = Trueprint(N)

First check, if N == 2 is unnecessary since there's already a block before that handles all the cases where N is prime so it can be removed. That said having it there doesn't cause any harm.

The next block that checks if N is divisible by a should terminate the recursion. Since you know that N isn't prime you should just stop there.

Final block that gets executed when N is not divisible by a should do the recursion instead. As it stands now the recursion stops as soon as N % a != 0 which is clearly wrong.

Here's a working sample with above modifications and cleanup:

defis_prime(N, a=2):
    if N <= 1:
        returnelif a >= N:
        print(N)
    elif N % a != 0:
        is_prime(N, a + 1)

Solution 5:

to print the list of prime numbers between a given range

l=[]
defprimenum(x,y):
    global l
    if x==y:
        print(l)
    else:
        m=0for i inrange(1,x+1):   
            if x%i==0:
                m+=1if m==2or x==1:
            l+=[x,]
            return primenum(x+1,y)
        else:
            primenum(x+1,y)