如何在python中生成第1000个素数? [英] How to generate the 1000th prime in python?
问题描述
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 个素数.我如何修改我的代码来这样做.在此先感谢您的帮助.
I'm trying to generate the 1000th prime number only through the use of loops. I generate the primes correctly but the last prime i get is not the 1000th prime. How can i modify my code to do so. Thank in advance for the help.
我现在明白如何解决这个问题了.但是有人可以解释为什么下面的代码不起作用吗?这是我在这里发布第二个之前写的代码.
I understand how to do this problem now. But can someone please explain why the following code does not work ? This is the code I wrote before I posted the second one on here.
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 循环 - 无需再测试任何数字.
If i%k==0, then i is not a prime. If we detect that it's not a prime, we should (a) not print it out, (b) not increment the counter of found primes and (c) we indeed should break out from the for loop - no need to test any more numbers.
另外，我们可以不测试 i%2，而是增加 2，从 3 开始 - 然后它们都是奇数，通过构造.
Also, instead of testing i%2, we can just increment by 2, starting from 3 - they will all be odd then, by construction.
所以，我们现在有
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 循环没有过早中断，则执行.
The else after for gets executed if the for loop was not broken out of prematurely.
它有效，但它太难了，所以比必要的要慢得多.它通过它下面的所有数字来测试一个数字，但它足以测试它的平方根.为什么?因为如果一个数字n == p*q，p和q介于1和n之间，那么 p 或 q 中的至少一个不会大于 n 的平方根:如果它们都大于，他们的乘积将大于 n.
It works, but it works too hard, so is much slower than necessary. It tests a number by all the numbers below it, but it's enough to test it just up to its square root. Why? Because if a number n == p*q, with p and q between 1 and n, then at least one of p or q will be not greater than the square root of n: if they both were greater, their product would be greater than 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 秒，对于 20004.89 秒(3000 - 12.15 秒).但是 sqrt 生成 3000 个素数只需要 0.21 秒，生成 10,000 个素数需要 0.84 秒，生成 20,000 个素数需要 2.44 秒(增长顺序 ~n2.1...2.2 vs. ~ n1.5).
Just try running it with range(2,i) (as in the previous code), and see how slow it gets. For 1000 primes it takes 1.16 secs, and for 2000 – 4.89 secs (3000 – 12.15 ses). But with the sqrt it takes just 0.21 secs to produce 3000 primes, 0.84 secs for 10,000 and 2.44 secs for 20,000 (orders of growth of ~ n2.1...2.2 vs. ~ n1.5).
上面使用的算法称为试验划分.要使其成为最佳试验部门，还需要进行一项改进，即仅通过素数进行测试.一个例子可以在这里看到，其中运行速度提高了大约 3 倍，并且具有更好的 ~ n1.3 经验复杂度.
The algorithm used above is known as trial division. There's one more improvement needed to make it an optimal trial division, i.e. testing by primes only. An example can be seen here, which runs about 3x faster, and at better empirical complexity of ~ n1.3.
然后是 Eratosthenes 的筛子，其中 ~n1.1，用于产生 n 个素数，测量到 n = 1,000,000 个素数):
Then there's the sieve of Eratosthenes, which is quite faster (for 20,000 primes, 12x faster than "improved code" above, and much faster yet after that: its empirical order of growth is ~ n1.1, for producing n primes, measured up to n = 1,000,000 primes):
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 倍，在此范围内为在这里测试.
The truly unbounded, incremental, "sliding" sieve of Eratosthenes is about 1.5x faster yet, in this range as tested here.
这篇关于如何在python中生成第1000个素数?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
