Producing primes in python: how is my logic wrong

Question

I'm starting a computer science program in the fall and I'm trying to build my programming chops a little before starting.

I'm going through the MIT OCW 6.0 problems and the first is to produce the 1000th prime number. Obviously, I want to produce my own code, so I'm wondering where my logic is going wrong.

counter = 1
primes = [2]
n = 3
while counter < 1000:
    for i in range(2, n):
        if n % i == 0:
        break
        else:
            primes.append(n)
            counter = counter + 1
    n = n + 1

print primes

You guys are amazing, so I won't explain every line here, but the gist of my logic is that I want this loop to start at n. If n is prime, add it to the list and add 1 to the counter, if not move on to the next number. Lastly, print the list, ending in the 1000th prime.

Look, I know this is "brute force" and I know there are Sieves out there and more complicated logic, but I want this to work in this way. Right now, I'm getting a lot of numbers repeated and no where near the 1000th prime.

Thanks guys. This is my first question, but I'm sure there will be more to come.

Your indentation is awry there. Where is that else clause? — BrenBarn
– BrenBarn, Commented Jun 28, 2013 at 4:21
@JonathonReinhart For python 2 anyway (which this question is using) — TerryA
– TerryA, Commented Jun 28, 2013 at 4:26

AMADANON Inc. · Accepted Answer · 2013-06-28 04:33:36Z

2

Your logic was right, your blocks were not. The break should be indented (under if n % i) and the else should be unindented, so it's the else for the for loop - i.e. numbers are only added if NONE of the primes are it's factor, instead of once for EACH of the primes are it's factor.

counter = 1
primes = [2]
n = 3
while counter < 1000:
    for i in range(2, n):
        if n % i == 0:
           break
    else:
        primes.append(n)
        counter = counter + 1
    n = n + 1

print primes

You can save time by only dividing n by (the list of primes so far), instead of all numbers - simply replace range(2, n) with primes

edited Jun 28, 2013 at 4:33

answered Jun 28, 2013 at 4:27

AMADANON Inc.

5,92924 silver badges32 bronze badges

Sign up to request clarification or add additional context in comments.

10 Comments

Jonathon Reinhart Over a year ago

I despise the for/else construct in Python.

Amber Over a year ago

@JonathonReinhart Any particular reason? It's a concise way to do something that otherwise generally requires an extra variable or function.

Jonathon Reinhart Over a year ago

@Amber Because they re-used the else keyword, where they should have introduced another one. for ... andthen makes way more sense to me. Just reading it, I almost always get it backwards from the way it actually works (else executes iff for completes normally).

Jonathon Reinhart Over a year ago

@Amber I like the concept, just hate the keyword. It's just quite different from an else associated with an if. There, the else body executes only if the if body doesn't execute. Before I read up on for..else, I assumed the else only executed if the for never executed once.

AMADANON Inc. Over a year ago

I don't tend do use it much, myself, but when I work with other people's code, I tend to apply the minimum reasonable change to fix the problem. That rule (of mine) applies in this case.

|

spicavigo · Accepted Answer · 2013-07-01 06:32:19Z

0

There were a couple of mistakes. Here is my version of your code

counter = 1
primes = [2]
n = 3
while counter < 1000:
    flag = 0
    for i in range(2, n):
        if n % i == 0:
            flag = 1
            break
    if flag==0:
        primes.append(n)
        counter = counter + 1
    n = n + 1

print primes

You can run the aboce code here http://codebunk.com/bunk#-Iy8aps3Zy7woREB64VF

EDIT: You do not need to check divisibility with numbers from 2 to n. Maybe change it to 2 to n^0.5

edited Jul 1, 2013 at 6:32

answered Jun 28, 2013 at 7:11

spicavigo

4,2441 gold badge25 silver badges28 bronze badges

4 Comments

Will Luce Over a year ago

Thank you. It's good to know that my logic wasn't the problem. Why did you choose to lose the flag?

spicavigo Over a year ago

"Why did you choose to lose the flag?" - I didn't get what you are saying.

Will Luce Over a year ago

Should have said, "Why did you choose to USE the flag?"

spicavigo Over a year ago

TO signify that I the inner loop did not end naturally but rather I broke out of it, i.e., I found a number which divides n

Collectives™ on Stack Overflow

Producing primes in python: how is my logic wrong

2 Answers 2

10 Comments

4 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

10 Comments

4 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related