10001番目の素数を見つける（Pythonで）？

Question

私は現在、erasthoneseの篩の実装を使用しようとしていますが、素数の長いリストを見つけるのに非常に時間がかかります。

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] 

私はふるいににどのような価値を実行する必要がありますし、ハードコードに試みたが、私は第一万二要素を見つけることができるようにうまくいけば、それは十分な長さです。ランタイムは現時点では大きな問題ですので、ランタイムを切ったり、何か他のことをすることについてのヒントやアドバイスは感謝しています。

Answer 1

特にこのコードを改善することに興味がある場合、最初にできることは非素数を格納するためにsetを使用することです。

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 

これにより、リスト内の数字の繰り返しが防止され、リスト内の検索が高速になります。これにより、実行時間が大幅に向上します。

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 

は今10001首相が達成可能である見つける：

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