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)
``````

## All 6 Replies

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.