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倍,在这个测试范围内.