CODEWITHSUNDEEP
pythonrecursionprimes
Harvey
Harvey

Reputation: 11

What’s wrong with my recursion for finding primes? (Python)

I’m trying to create a program that lists all the primes below an inputted number, and I came up with the code:

def primes():
    num = 20

    numlist = list(range(1,num+1))
    i = len(numlist)

    for j in numlist[2:]:
        ans = divisible(j,i)

        if ans:
            numlist.remove(j)
            print(numlist)

def divisible(m,n):

    if m!=n and m%n==0:
        return True

    elif n == 1:
        return False

    else:
        divisible(m, n-1)

primes()

(I used an in-browser IDE so the num part was a proxy for the input.)

My idea was to create a separate function divisible() that when inputted two ints, m and n, would check if n divides m. I'm not sure if I was right in my recursion, but I wrote divisible(m,n-1) the idea was that it would iterate through all the integers from n downward and it would return True if any n divided m, or False if it reached 1.

In the main code, m iterated through all the numbers in a list, and n is the total number of elements in the same list. I put the print(numlist) inside the if statement as an error check. The problem I’m having is nothing is printing. The code returned literally nothing. Is there something I’ve missed in how recursion works here?

Upvotes: 1

Views: 31

Answers (2)

cdlane
cdlane

Reputation: 41895

There's a lot wrong here:

You've made a common beginner's recursion error in that you have a recursive function that returns a value, but when you call it recursively, you ignore the returned value. You need to deal with it or pass it along.

It seems like this modulus is backward:

if ... and m%n==0:

Maybe it should be:

if ... and n % m == 0:

You're code doesn't appear to be calculating primes. It's looks like it's calculating relative primes to n.

You start your list of numbers at 1:

numlist = list(range(1,num+1))

But you start testing at index 2:

for j in numlist[2:]:

Which is the number 3 and you never check the divisibility of the number 2.

Even with all these fixes, I don't feel your algorithm will work.

Upvotes: 1

San
San

Reputation: 463

Your divisible function doesn't return anything if it falls into else part. change it as

def divisible(m, n):
    if m!=m and m%n==0:
        return True
    elif n==1 :
        return False
    else:
        return divisible(m,n-1)

This should work

Upvotes: 0

Related Questions