Finding the 10001st prime number (in python)? [dup

Question

This question already has an answer here:

• Fastest way to list all primes below N 31 answers

I'm currently trying to use an implementation of the sieve of erasthonese, but it still takes a very long time to find a long list of prime numbers.

def sieve(n=1000000):
    not_prime = []
    prime = []
    for i in range(2, n+1): 
        if i not in not_prime:
            prime.append(i) 
            for j in range(i*i, n+1, i): 
                not_prime.append(j) 
    return prime[10002]

I tried to hard code to what value the sieve should run to, and hopefully, it's long enough so that I can find the 10002nd element. Runtime is a big problem at the moment, so any tips or advice on cutting runtime down or anything else is appreciated.

Answer 1

If you are interested in improving this code in particular, then the first thing you could do is use a set to store the non primes.

def sieve_set(n=1000000):
    not_prime = set()
    primes = []
    for i in range(2, n+1): 
        if i not in not_prime:
            primes.append(i) 
            for j in range(i*i, n+1, i): 
                not_prime.add(j)

    return primes

This prevents repetition of numbers within the list, and makes searches within the list fast. This will vastly improve your run time.

In [1]: %timeit -n 1 -r 1 sieve(10000)
1 loops, best of 1: 775 ms per loop

In [2]: %timeit -n 1 -r 1 sieve_set(10000)
1 loops, best of 1: 5.85 ms per loop

Now finding the 10,001 prime is achievable:

In [3]: %timeit sieve_set(105000)
10 loops, best of 3: 26.6 ms per loop

In [4]: sieve_set(105000)[10000]
Out[4]: 104743