如何在Python中生成第1000个素数?

Question

count = 0
i = 11

while count <= 1000 and i <= 10000:
    if i%2 != 0:
       if (i%3 == 0 or i%4 == 0 or i%5 == 0 or i%6 == 0 or i%7 == 0 or i%9 == 0):
           continue
       else:
           print i,'is prime.'
           count += 1
    i+=1

我正在尝试通过循环生成第1000个质数。我生成的质数是正确的，但我得到的最后一个质数并不是第1000个质数。我该如何修改我的代码来实现这个目标呢？提前感谢大家的帮助。

补充说明：我现在明白如何解决这个问题了。但能不能请大家解释一下，为什么下面的代码不工作？这是我在这里发布第二个代码之前写的代码。

count = 1
i = 3
while count != 1000:
    if i%2 != 0:
       for k in range(2,i):
          if i%k == 0:
            print(i)
            count += 1
            break
     i += 1

Answer 1

你确定你检查质数的方法是对的吗？一个常见的解决办法是写一个单独的“isPrime”函数，这个函数你可以确认它是有效的。

def isPrime(num):
    i = 0
    for factor in xrange(2, num):
        if num%factor == 0:
            return False
    return True

（还有一些方法可以让上面的函数更有效，比如只检查奇数，或者只检查小于平方根的数字等等。）

然后，要找到第n个质数，就要数出所有的质数，直到找到为止：

def nthPrime(n):
    found = 0
    guess = 1
    while found < n:
        guess = guess + 1
        if isPrime(guess):
            found = found + 1
    return guess

Answer 2

这里有几个明显的问题。首先，因为你是从11开始的，所以你已经跳过了前5个质数，因此计数应该从5开始。

更重要的是，你的质数检测算法根本行不通。对于这种简单的“埃拉托斯特尼筛法”质数检测，你必须记录所有小于i的质数。例如，你的算法会认为11 * 13 = 143是质数，但显然它不是。

PGsimple1 这里是你想要实现的质数检测的正确版本，但那里的其他算法要快得多。

Answer 3

我们来看看。

count = 1
i = 3
while count != 1000:
    if i%2 != 0:
       for k in range(2,i):
          if i%k == 0:        # 'i' is _not_ a prime!
            print(i)       # ??
            count += 1     # ??
            break
     i += 1          # should be one space to the left,
                     # for proper indentation

如果 i%k==0，那么 i 就不是一个质数。如果我们发现它不是质数，我们应该 (a) 不 打印出来，(b) 不 增加找到的质数计数器，(c) 我们确实应该退出 for 循环——没有必要再测试其他数字了。

另外，我们可以不测试 i%2，而是从 3 开始，每次加 2——这样得到的数字都是奇数。

所以，现在我们有了

count = 1
i = 3
while count != 1000:
    for k in range(2,i):
        if i%k == 0:       
            break
    else:
        print(i)
        count += 1
    i += 2        

在 for 循环后面的 else 只有在 for 循环没有提前退出时才会执行。

这个方法可以用，但效率太低，速度比必要的要慢很多。它会用所有小于这个数字的数字来测试，但其实只需要测试到它的平方根就够了。为什么呢？因为如果一个数字 n == p*q，其中 p 和 q 在 1 和 n 之间，那么至少有一个 p 或 q 不会大于 n 的平方根：如果它们都大于平方根，它们的乘积就会大于 n。

所以 改进后的代码是：

from math import sqrt

count = 1
i = 1
while count < 1000:
    i += 2
    for k in range(2, 1+int(sqrt(i+1))):
        if i%k == 0:       
            break
    else:
        # print(i) ,
        count += 1
        # if count%20==0: print ""
print i

试着用 range(2,i)（就像之前的代码那样）运行一下，看看它有多慢。对于1000个质数，它需要1.16秒，2000个质数需要4.89秒（3000个质数需要12.15秒）。但是使用平方根后，生成3000个质数只需0.21秒，生成10,000个质数需要0.84秒，生成20,000个质数需要2.44秒（增长速度的比较是 ~ n2.1...2.2 对比 ~ n1.5）。

上面使用的算法被称为 试除法。为了使其成为最优的试除法，我们还需要一个改进，即只用质数进行测试。一个例子 可以在这里看到，这个方法 运行速度快了大约3倍，并且在实际复杂度上更好，达到 ~ n1.3。

---

接下来是 埃拉托斯特尼筛法，它 速度相当快（对于20000个质数，比上面的“改进代码”快12倍，之后速度更快：它的实际增长速度为 ~ n1.1，用于生成 n 个质数，测量到 n = 1,000,000 个质数）：

from math import log

count = 1 ; i = 1 ; D = {}
n = 100000                        # 20k:0.20s 
m = int(n*(log(n)+log(log(n))))   # 100k:1.15s 200k:2.36s-7.8M 
while count < n:                  #            400k:5.26s-8.7M 
        i += 2                    #            800k:11.21-7.8M 
        if i not in D:            #            1mln:13.20-7.8M (n^1.1)
            count += 1
            k = i*i
            if k > m:  break      # break, when all is already marked
            while k <= m:
                D[k] = 0 
                k += 2*i
while count < n:
        i += 2
        if i not in D: count += 1
if i >= m: print "invalid: top value estimate too small",i,m ; error
print i,m  

真正无限制的 增量“滑动”埃拉托斯特尼筛法 在这个范围内测试时速度还快了约1.5倍。