Skip to main content
 首页 » 编程设计

python之谁能帮我找出我写的素数生成器函数中的错误

2024年12月31日13小虾米

有人可以帮助我为什么在我列出前 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