CODEWITHSUNDEEP
pythonprimes
chubbycantorset
chubbycantorset

Reputation: 113

Prime generator in python returns multiple composites instead of primes

I'm fairly new to Python, and am trying to practice programming by doing Project Euler problems. In order to solve the 7th problem, I decided to first build a simple prime generating function using for loops, which doesn't seem to work.

Here's my code:

primes = [2]

for n in range(2, 10):
    for m in range(2, n):
        if not(n % m):
            primes.append(n)

print primes

The output is [2,4,6,6,8,8,9] instead of what I intended, i.e. [2,3,5,7]. The math seems correct to me: Pick a natural number, n, bigger than two. For all natural numbers m bigger than one, but smaller than n, check if n is divisible by m. If not, add n to the list of primes. Can anyone please tell me what's wrong with my code?

P.S. While I know there are several other (and better) ways of generating primes, I am interested in making my approach (code) work.

Upvotes: 1

Views: 85

Answers (1)

lunixbochs
lunixbochs

Reputation: 22415

not(n % m) tells you if a number is not prime.

You also need to do it for every candidate factor before you know if the number is prime or not.

Python has a very handy mechanism for this in for: else:, which only runs the else block if you did not break from the for.

primes = []
for n in range(2, 10):
    for m in range(2, n):
        if not(n % m):
            break
    else:
        primes.append(n)

You can test primality in a similar way with a generator expression:

prime = not(any(n % m == 0 for m in range(2, n)))

Remember range is inefficient in Python 2.x, as it generates the entire list of numbers before starting iteration. Use xrange unless you're on Python 3.x

Upvotes: 3

Related Questions