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.

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!

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.

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.