I've been set an assignment to find all the prime numbers smaller than N

We've been told to first create a function to test if it is divisble by any numbers in my primes list
and then second to create a function to test each integer from 2 to N, then using the previous function find all the primes and print them.

i've created this, however my code outputs all the numbers from 2 to N rather than just the primes.
I can't figure out why.

def is_divisible(n, primes):
    """
    Tests to see if a number is divisible by any number in the list of primes
    """
    for p in primes:
        if n % p == 0:
            return False
    return True

def find_primes(N):
    """
    Returns list of primes smaller than N
    """

    primes=[]
    for n in range(2, N+1):
        is_divisible(n,primes)
        if True:
            primes.append(n)
    print(primes)



find_primes(20)

The problem is that you are calling the is_divisible() function, and then, on a separate line, testing whether True is true, which will always be the case. What you want to do is call the function as part of the if: clause itself:

    primes=[]
    for n in range(2, N+1):
        if is_divisible(n, primes):
            primes.append(n)
    print(primes)

This has the effect that the return value of the function is used as the condition of the if: statement.

Edited 3 Years Ago by Schol-R-LEA

You are an absolute lifesaver! I've been trying this for literally hours! Thank you so much. Coding is very annoying when it is one little thing that stops everything working!

Edited 3 Years Ago by 123pythonme

I am now trying to make the code run faster as I have to find primes up to 10^6.

I am trying to make it so i only check numbers that are odd and less than the sqroot of N.

My code now only displays [2,3] as primes of 20.

def is_divisible(n, primes):
    """
    Tests to see if a number is divisible by any number in the list of primes
    """
    #No prime numbers less than 2
    if n < 2:
        return False
    for p in primes:
        if n % p == 0:
            return False
    return True



def find_primes(N):
    """
    Returns list of primes smaller than N
    """

    primes=[]
    for n in range(2, int(N**0.5)+1):
        if is_divisible(n, primes):
            primes.append(n)
    print(primes)


find_primes(20)

The part of the code I have altered is this.

for n in range(2, int(N**0.5)+1):

What reasoning would there be that it won't display all of the primes?

I would strongly suggest that you print "p" to see what it contains and then look at what you are sending to the function

for p in primes:
    if n % p == 0:
        return False

Also run this test ...

N = 20
# list() needed for Python3
# since range() is now a generator object
print(list(range(2, int(N**0.5)+1)))

''' result ...
[2, 3, 4]
'''

I don't think this is what you want.

This question has already been answered. Start a new discussion instead.