Trouble finding the 1000th prime using python

Question

I am self learning Python from the MIT open courseware website. I am having trouble completing this assignment using only the information learned in the lectures. The last thing I learned was iterations using the "While" and "For" loops. I have not learned functions yet. Is it possible to write a program that computes and prints the 1000th prime number using only this?

Here is my code so far:

count = 0
prime = []
candidate = []
x = 2
y = 1
while count < 1000:
    x = x+1
    if x > 1:
        if x%2 != 0:
            if x%3 != 0:
                if x%5 != 0:
                    if x%7 != 0:
                        if x%11 != 0:
                            if x%13 != 0:
                                candidate.append(x)

Needless to say: your approach has some problems scaling.. I suggest you google for some different approaches to calculating prime numbers first. — Martijn Pieters, Aug 01 '13 at 10:49
I haven't gotten that far because I wanted to know if there was a more efficient way in doing this. — AvP, Aug 01 '13 at 10:49
Look at the if statements you write. Each checks if it is divisible by a prime smaller than x. These primes are exactly what you calculated in the previous iterations and have probably stored in the primes or candidate list. So you'll probably also have to loop over this list, inside the while loop. — Vortexfive, Aug 01 '13 at 10:51
possible duplicate of [Finding the nth prime number using Python](http://stackoverflow.com/questions/3885937/finding-the-nth-prime-number-using-python) or [Generating the 1000th Prime in Python](http://stackoverflow.com/questions/15400108/generating-the-1000th-prime-in-python) — Inbar Rose, Aug 01 '13 at 10:53
Try googling the keyword "sieve of Eratosthenes", then try implementing it in code, it will be useful in other problems from project Euler. — Pawel Miech, Aug 01 '13 at 11:01

poke · Accepted Answer · 2013-08-01T11:41:04.260

Your code has a few problems which I’ll try to point out:

count = 0
prime = []          # this is obviously meant to collect all primes
candidate = []      # what is this supposed to do then though?
x = 2
y = 1               # never used
while count < 1000: # you start at `count = 0` but never increase the count
                    # later on, so would loop forever
    x = x+1
    if x > 1: # x is always bigger than 1 because you started at 2
              # and only increase it; also, you skipped 2 itself
        if x%2 != 0:                      # here, all you do is check if the
            if x%3 != 0:                  # number is dividable by any prime you
                if x%5 != 0:              # know of
                    if x%7 != 0:          # you can easily make this check work
                        if x%11 != 0:     # for any set (or list) of primes
                            if x%13 != 0: #
                                candidate.append(x) # why a candidate? If it’s
                                                    # not dividable by all primes
                                                    # it’s a prime itself

So, building on this, you can make it all work:

primes = [2] # we're going to start with 2 directly
count = 1    # and we have already one; `2`
x = 2
while count < 1000:
    x += 1
    isPrime = True          # assume it’s a prime
    for p in primes:        # check for every prime
        if x % p == 0:      # if it’s a divisor of the number
            isPrime = False # then x is definitely not a prime
            break           # so we can stop this loop directly

    if isPrime:             # if it’s still a prime after looping
        primes.append(x)    # then it’s a prime too, so store it
        count += 1          # and don’t forget to increase the count

Where did the p in the for loop come from?

for x in something is a construct that will loop over every element in something and for each iteration it gives you a variable x that will contain the current value. So for example the following will separately print 1, 2, 3.

for i in [1, 2, 3]:
    print(i)

Or for a list of primes, for p in primes will loop over all your stored primes and in each iteration p will be one prime from the list.

So the whole check will essentially loop over every known prime, and for each prime it will check if said prime is a divisor of the number. And if we find one prime for which this is the case, we can abort the loop, because the current number is definitely not a prime itself.

I am still confused as to how the for loop checks to see if it is a prime. Where did the p in the for loop come from and what does it mean to x%p? — AvP, Aug 01 '13 at 11:31
You had x%2 etc in your code - the modulus operator. for p in primes gives p each number in primes — doctorlove, Aug 01 '13 at 11:35
I understand that it is the modulus operator, but I am confused what "p" is. Is it arbitrarily assigned or does it have a function? — AvP, Aug 01 '13 at 11:41
Thanks for revising your answer, it is a lot clearer now :). — AvP, Aug 01 '13 at 11:44

score 0 · Answer 2 · answered Aug 01 '13 at 11:00

0

Without doing the whole thing for you, as has been said you are building up a list of primes, in prime so you could use that instead of hardcoding things to check.

 prime = []
 x = 2
 while len(prime) < 1000:
     if *** check here ***
        prime.append(x)
     x = x + 1

answered Aug 01 '13 at 11:00

doctorlove

18,872
2
46
62

The main problem I have is trying to find a check that works for every prime number... it seems impossible. I am also wondering if I should be majoring in Computer Engineering if I am struggling with simple programming. – AvP Aug 01 '13 at 11:06
Don't panic - hard things are worth doing. I would use if all([x%p != 0 for p in prime]):prime.append(x) but I presume you haven't met "any" yet - so use Steve Barnes' way insead. – doctorlove Aug 01 '13 at 11:12

Steve Barnes · Answer 3 · 2013-08-01T11:39:29.420

0

import time    
start = time.time()

primes = [2,]  # Initial list of primes
l = 1  # No in the list
n = 3  # First candidate
while l < 10000:  # Target No
    Ok = True  # Assume it is
    for p in primes[1:1+l//2]:  # Check all in the first half of the list 
       if (n % p) == 0:  # Divides exactly
           Ok = False    # So not prime
           break         # Skip the rest
    if Ok:  # It was a prime
       primes.append(n)  # Add it
       l += 1            # and the count
       #print n
    n += 2  # Next non-even number
end = time.time()
print primes[-1]
print 'took', end-start

edited Aug 01 '13 at 11:39

answered Aug 01 '13 at 11:09

Steve Barnes

27,618
6
63
73

2

Can we say primes = [2] instead? I'm sure 1 isn't prime. And then you can just say for p in primes – doctorlove Aug 01 '13 at 11:13
1

Yes, [1 is not a prime](http://math.stackexchange.com/questions/120/is-1-a-prime-number). – poke Aug 01 '13 at 11:21
Sorry - showing my age now 1 was a prime for a few thousand years then was excluded in the late 1950s - when a lot of the books I learnt from were printed - modifications going in. – Steve Barnes Aug 01 '13 at 11:35

score 0 · Answer 4 · answered Aug 01 '13 at 11:28

0

Of course there is a neater way than chaining all those ifs, you can use all

prime = []
x = 1
while len(prime) < 1000:
    x += 1
    if all(x%p for p in prime):
        prime.append(x) 

print prime

answered Aug 01 '13 at 11:28

John La Rooy

295,403
53
369
502

Trouble finding the 1000th prime using python

4 Answers4