寻找第n个质数

Question

我搞不懂为什么这个不行。请帮帮我。

from math import sqrt

pN = 0 
numPrimes = 0
num = 1

def checkPrime(x):
   '''Check\'s whether a number is a prime or not'''
   prime = True
   if(x==2):
      prime = True
   elif(x%2==0):
      prime=False
   else:
      root=int(sqrt(x))
      for i in range(3,root,2):
         if(x%i==0):
            prime=False
            break
   return prime

n = int(input("Find n number of primes. N being:"))

while( numPrimes != n ):
   if(  checkPrime( num ) == True ):
      numPrimes += 1
      pN = num
      print("{0}: {1}".format(numPrimes,pN))
   num += 1

print("Prime {0} is: {1}".format(n,pN))

Answer 1

和@Braxton在评论中说的不同，埃拉托斯特尼筛法这个算法其实可以很容易地调整，用来生成无限的质数（比如可以作为一个潜在的无限生成器，然后根据需要进行限制，比如用itertools.slict）。

你可以查看这个链接，里面有一个用Python实现的无限埃拉托斯特尼筛法（记得参考评论中的改进建议，包括我的建议；-)）。或者你也可以在这里查看经过最终编辑的食谱版本（可惜在这个谷歌书籍的链接中讨论部分被删减了，但至少解决方案的代码都在那儿；-)）。

Answer 2

你需要把

root=int(sqrt(x))

改成

root=int(sqrt(x))+1

（以9为例，int(sqrt(9))的结果是3，而range(3, 3, 2)的结果是[]，你确实想要测试一下能不能用3来除！）

从技术上讲，1也不是一个质数。加上

if(x<=1):
   prime = False

你会得到和这个链接相同的结果：http://www.rsok.com/~jrm/first100primes.html