查找10001素數（在python中）？

我目前正在嘗試使用erasthonese篩的實現，但它仍然需要很長時間才能找到一長串素數。查找10001素數（在python中）？

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]

我試圖硬編碼到什麼樣的價值篩應運行，並希望，這是足夠長的時間，這樣我可以找到第一萬零二元素。運行時目前是個大問題，所以關於減少運行時間或其他方面的任何提示或建議都是值得讚賞的。

來源

2016-05-19 Peter

如果您有興趣特別改進此代碼，那麼您首先可以使用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

現在找到10,001素是可以實現的：

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

來源

2016-05-19 01:43:37 donkopotamus

查找10001素數（在python中）？

回答

相關問題