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

## Recommended Answers

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:

`` …``

Use a few temporary print() functions to see your problems.

The brute force algorithm will take too much time with prime numbers in the higher ranges. So will the many calls to function is_divisible(). See the code snippet:

## 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 1.21 million developers, IT pros, digital marketers, and technology enthusiasts learning and sharing knowledge.