Find out 20th, 30th, nth prime number. (I'm getting 20th but not 30th?) [Python]

Question

The question is to find the 1000th prime number. I wrote the following python code for this. The problem is, I get the right answer for the 10th , 20th prime but after that each increment of 10 leaves me one off the mark. I can't catch the bug here :(

count=1            #to keep count of prime numbers
primes=()          #tuple to hold primes
candidate=3        #variable to test for primes
while count<20:
    for x in range(2,candidate):
        if candidate%x==0:
            candidate=candidate+2
        else : pass
    primes=primes+(candidate,)            
    candidate=candidate+2
    count=count+1
print primes        
print "20th prime is ", primes[-1]

In case you're wondering, count is initialised as 1 because I am not testing for 2 as a prime number(I'm starting from 3) and candidate is being incremented by 2 because only odd numbers can be prime numbers. I know there are other ways of solving this problem, such as the prime number theorem but I wanna know what's wrong with this approach. Also if there are any optimisations you have in mind, please suggest.

Thank You

Answer 1

I don't think this is testing what you think it's testing. It looks like you're trying to say "for each number between 2 and my candidate, check to see if the candidate is evenly divisible by that number". However, when you find a prime (candidate%x == 0), you're only incrementing the candidate-- you still need to start your "for x in ..." loop over again, since the candidate has changed.

That's what I can see from the code as written; there are of course lots of other ways and other optimizations to use here.

Answer 2

There is lots (!) to be improved with your Python code, but to answer your specific question:

When you have found a divisor (candidate % x == 0), you increment the candidate, but you don't do anything about x. This can lead to two problems:

1. candidate might have a divisor, but it's smaller than any x that gets tested -- because testing in the next iteration of the loop starts with x being one higher than the value x had before; not at 2.
2. candidate might have a divisor, but it's larger than x ever gets, because you take x from the values from 2 to the value candidate had when you started the loop.

Answer 3

As for optimizations, if you're definite that you want to follow this implementation, you could avoid looking at numbers that:

1. end in 5, since they are divisible by 5.
2. are comprised by the same digits, e.g. 22, 33, 44, 55, 66, etc., since they are divisible by 11.

Don't forget to add 5 and 11 as primes though!

Answer 4

Unless I'm very much mistaken, you are always adding the current candidate to the list of primes, regardless of whether a divisor has been found or not. Your code to append to the list of primes (putting aside the immutable tuple comment made earlier) is outside of the test for integer divisors, and therefore always run.

Answer 5

It's good to know that every prime number bigger than 3 can be written as: 6k-1/+1.

When you are looking for the next candidate, you can always write something like this (code snippet is in C):

a=1;
...
candidate=6*k+(a=(a==-1)?1:-1);
if(a==1){
           k++;
}

And a function I've used not so long ago to determine the nth prime number, where LIM is the nth number you are looking for (C code):

int sol2(){
        int res,cnt,i,k,a;
        res=-1;
        i=1;
        cnt=3;
        k=1;
        a=1;
        while (1){
                if (util_isprime(cnt)){
                        i++;
                        if (i==LIM){
                                res=cnt;
                                break;
                        }
                }
                /* 6k+/-1 starting from 6*1-1 */
                cnt=6*k+(a=(a==-1)?1:-1);
                if(a==1){
                        k++;
                }
        }
        return res;
}

Answer 6

in the statement:

for x in range(2,candidate)

you can reduce the number of iterations by scanning up to sqrt(candidate)

If candidate is divisible by x, then we can write candidate=x*b for some b. If x is less than or equal to b, then x must be smaller than or equal to the square root of candidate

Answer 7

If you want anything remotely efficient, do the Sieve of Eratosthenes - it's as simple as it's old.

MAX = 10000
candidates = [True] * MAX
candidates[0] = False
candidates[1] = False

primelist = []
for p,isprime in enumerate(candidates):
    if isprime:
        primelist.append(p)
        for n in range(2*p,MAX,p):
            candidates[n] = False

print primelist[1001]

Answer 8

There is a nice Sieve of Eratosthenes generator implementation in test_generators.py:

def intsfrom(i):
     while 1:
         yield i
         i += 1

def firstn(g, n):
     return [g.next() for i in range(n)]

def exclude_multiples(n, ints):
     for i in ints:
         if i % n:
             yield i    

def sieve(ints):
     prime = ints.next()
     yield prime
     not_divisible_by_prime = exclude_multiples(prime, ints)
     for p in sieve(not_divisible_by_prime):
         yield p

primes = sieve(intsfrom(2))

>>> print firstn(primes, 20)
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71]

Answer 9

FYI... I solved it with the following code, though it can be optimised much much more, I just wanted to solve it in this manner first. Thanks everyone for your help.

from math import *
primes=[2,3]
count=2
testnumber=5
while count<1000:

    flag=0
    for x in range(2,testnumber):
        if x<=sqrt(testnumber):
            if testnumber%x==0:
                #print testnumber , "is not a prime"
                flag=1

            else : pass
    if flag!=1:
        #print testnumber , "is a prime"
        primes=primes+[testnumber]
        count=count+1
    testnumber=testnumber+2


#print primes
print "1000th prime is ", primes[-1]

I will now look at all the other algorithms mentioned by you all