1

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.

Will Luce
  • 1,781
  • 3
  • 20
  • 33

2 Answers2

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

AMADANON Inc.
  • 5,753
  • 21
  • 31
  • 3
    I *despise* the `for`/`else` construct in Python. – Jonathon Reinhart Jun 28 '13 at 04:28
  • 1
    @JonathonReinhart Any particular reason? It's a concise way to do something that otherwise generally requires an extra variable or function. – Amber Jun 28 '13 at 04:28
  • 2
    @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 Jun 28 '13 at 04:30
  • @JonathonReinhart Yes, because the idea is that you're scanning a sequence, and taking action in a particular circumstance (followed by a `break`). If that circumstance doesn't happen, then the `else` kicks in, because it's what else you do if you didn't break. – Amber Jun 28 '13 at 04:32
  • 2
    @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. – Jonathon Reinhart Jun 28 '13 at 04:34
  • @JonathonReinhart Okay, but I'd argue that's rather subjective - I find that the `else` usage with `for` makes sense, due to the narrative I just described. I would actually find `then` *more* confusing. – Amber Jun 28 '13 at 04:34
  • @Amber It also seems counter-intuitive to me, because in essence, the `break` statement inside of the `for` block transfers execution past `else` - just very different from any of the C-style languages I've grown up with :-) – Jonathon Reinhart Jun 28 '13 at 04:37
  • 1
    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. – AMADANON Inc. Jun 28 '13 at 04:49
  • it is way more important to stop at the sqrt of the number being tested, than just switch to primes. Or [do both](http://stackoverflow.com/a/17324422/849891). :) – Will Ness Jun 28 '13 at 16:39
  • Apart from, "Yes, do both", You are right - my vague instinct was that the number of primes less than N would be less sqrt(N), but that does not appear to be the case. If I was optimizing this fully, I would keep two lists of primes, one <= sqrt(candidate), one >. I would cache greaterthan[0]^2, to save square roots. I'd also write it in assembly :) – AMADANON Inc. Jul 01 '13 at 20:48
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

spicavigo
  • 4,116
  • 22
  • 28