查找特定的素數

Question

這是我實現查找特定質數：

import math 

def checkPrime(i): 
    if i == 3: 
     return True; 
    elif i == 2: 
     return True; 
    else: 
     count = 2; 
     prime = 2; 

     while count <= math.sqrt(i): 
      if (i % count == 0): 
       prime += 1; 
      count += 1; 

     if prime == 2: 
      return True; 
     else: 
      return False; 

x = 0; 
c = 2; 
while x < 10001: 
    if checkPrime(c) == True: 
     print c; 
     x += 1; 
    c += 1; 

我用這個來找到10,001st素數（我從Project Euclid了一個問題）。但是，這似乎並不是解決問題的有效方法。它佔用了大量的計算能力（從執行完成需要大約20秒的事實可以看出）。我自己解決了這個問題，但花費的時間很艱鉅。

完成此問題最有效的方法是什麼？

P.S：我打印出所有的素數，以保持只看到偏好。這不是必需的。

Answer 1

def fast_primes(max_n): 
    numbers = range(3, max_n+1, 2) 
    half = (max_n)//2 
    initial = 4 

    for step in xrange(3, max_n+1, 2): 
     for i in xrange(initial, half, step): 
      numbers[i-1] = 0 
     initial += 2*(step+1) 

     if initial > half: 
      return [2] + filter(None, numbers) 
start = 5 
tmp = [] 
while len(tmp) < 10001: 
    tmp=fast_primes(start) 
    start <<=1 

print tmp[10001] 

似乎相當快是我（把我的邊際計算機上0.02秒）