python - 如何在python中生成第1000个素数？

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

最佳答案

让我们来看看。

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之外，我们还可以从2开始按3进行递增-然后通过构造它们都将是奇数。

所以，我们现在有

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

如果没有过分打破else循环，则会执行for之后的for。

它可以工作，但是工作太辛苦，因此速度比必要的慢得多。它会通过下面的所有数字测试一个数字，但足以测试它的平方根。为什么？因为如果数字n == p*q和p和q在1和n之间，那么p或q中的至少一个将不大于n的平方根:如果二者均大于，则其乘积将大于n。

所以the improved code is:

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 ses)来说。但是，使用sqrt只需花费0.21秒即可产生3000个素数，花费10,000则只需0.84秒，花费20,000即可花费2.44秒(~ n的orders of growth与~ n对比)。

上面使用的算法称为trial division。要使其成为最佳的试用部门，还需要进行另一项改进，即仅按素数进行测试。一个示例can be seen here，即runs about 3x faster，其经验复杂度更高。

然后是the sieve of Eratosthenes，即is quite faster(对于20,000个素数，比上面的“改进代码”快12倍，但之后要快得多:它的经验增长顺序为~ n，用于产生~ 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

真正无界的incremental, "sliding" sieve of Eratosthenes快了1.5倍，在这里测试的这个范围内。

关于python - 如何在python中生成第1000个素数？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/15400108/