有人可以帮助我为什么在我列出前 25 个素数时在我的生成器中得到某些数字,如“27”和“35”?我知道有更有效的方法,如 Erathosthenes 筛法,但我担心这段代码中存在一些错误。谢谢你!
def next_prime():
num = 2
while True:
for i in range(1, num+1):
if (i != 1) and (num % i == 0):
# print(num, " is not prime")
num += 1
yield num
num += 1
primes = next_prime()
[print(next(primes)) for i in range(25)]
下面的输出——突出显示了一些合数
3 5个 7 11 13 17 19 23 27 29 31 35 37 41 43 47 53 59 61 67 71 73 79 83 87
请您参考如下方法:
你在 for 循环中 increment num,但你不能简单地这样做,因为 i 没有重置为 1,因此您错过了某些检查。
因此您应该break,然后递增num 并让循环检查下一个数字。因此,我们可以使用 for-else 仅在循环成功时产生一个数字(即没有到达 break 语句)。
现在将要发生的另一个问题是没有数是质数了。这是因为您的 range(1, num+1) includes num,并且数字始终可以被自身整除。因此,范围应介于 1(或更好的 2)和 num(不包括)之间:
def next_prime():
num = 2
while True:
for i in range(2, num):
if num % i == 0:
break
else:
yield num
num += 1
然而,上面的方法不是非常有效。我们可以使这种方式更快。例如,所有偶数,除了两个都不是素数,因此我们可以将其重写为:
def next_prime():
<b>yield 2</b>
<b>num = 3</b>
while True:
for i in range(2, num):
if not num % i:
break
else:
yield num
num += <b>2</b>
此外,对于数字 n,我们只需要检查 √n,因为如果 n 可以被数字 a 整除,并且 a 大于 n 的平方根,则存在一个数 b = n/a 小于平方根:
from math import sqrt, ceil
def next_prime():
yield 2
num = 3
while True:
for i in range(<b>3</b>, <b>ceil(sqrt(num))+1</b>, 2):
if not num % i:
break
else:
yield num
num += 2
