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.
所以改进的代码是:
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个素数,0.84秒为10,000和2.44秒20,000(增长订单的对比).~ n2.1...2.2~ n1.5
上面使用的算法称为试验分割.还需要进一步改进才能使其成为最佳的试验部门,即仅通过质数进行测试.这里可以看到一个例子,它的运行速度提高了约3倍,且经验复杂度更高 .~ n1.3
然后有埃拉托塞尼的筛,这是相当快(20,000素数,比"改进的代码"更快12X的上方,并且还快得多之后:其生长的经验顺序是,用于生产的素数,测量到Ñ = 1,000,000素数):~ n1.1n
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
Eratosthenes的真正无界,增量,"滑动"筛子的速度提高了约1.5倍,在此测试范围内.
A couple of problems are obvious. First, since you're starting at 11, you've already skipped over the first 5 primes, so count should start at 5.
More importantly, your prime detection algorithm just isn't going to work. You have to keep track of all the primes smaller than i for this kind of simplistic "sieve of Eratosthanes"-like prime detection. For example, your algorithm will think 11 * 13 = 143 is prime, but obviously it isn't.
这里的PGsimple1是您在此处尝试进行的素数检测的正确实现，但那里的其他算法要快得多。