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

发布时间：2020-12-16 23:38:11 所属栏目：Python 来源：网络整理

导读：count = 0i = 11while 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个素数.我正确地生成素

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,那么我不是素数.如果我们发现它不是素数,我们应该(a)不打印出来,(b)不增加发现的素数的计数器,(c)我们确实应该从for循环中脱离出来 – 不需要再测试任何数字.

此外,我们可以从3开始增加2,而不是测试i％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循环没有被过早地破坏,那么之后的执行将被执行.

它有效,但它的工作太难了,所以要慢得多.它会根据下面的所有数字来测试一个数字,但只要测试它的平方根即可.为什么？因为如果一个数字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秒).但是,sqrt只需要0.21秒的时间才能产生3000个素数,对于10,000和0.44秒,对于20,000(orders of growth?n2.1 … 2.2 vs.?n1.5),需要0.84秒.

上面使用的算法被称为trial division.还有一个进一步的改进需要使其成为最佳的试验划分,即仅通过素数测试.一个例子can be seen here,其中runs about 3x faster,更好的经验复杂性?n1.3.

那么the sieve of Eratosthenes是is quite faster(对于20,000个素数,比上面的“改进代码”要快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

真正无限的incremental,“sliding” sieve of Eratosthenes速度还快了1.5倍,在这个测试范围内.

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!