如何在 Python 中优化简单的素数生成器？

在 Python 中优化简单素数生成器

提供的 Python 代码旨在生成素数，但需要改进效率。

原始代码的问题：

1. 循环检查整除性，但即使找到除数，也会错误地打印计数。
2. Continue 语句终止当前迭代，但应替换为break，以便在找到除数时完全停止搜索。

改进的代码：

import math

def main():
    count = 3
    while True:
        isprime = True
        for x in range(2, math.ceil(math.sqrt(count)) + 1):
            if count % x == 0: 
                isprime = False
                break
        if isprime:
            print(count)
        count += 1

解释：

• 外部循环增加计数以测试下一个可能的素数。
• 内部循环现在运行到计数的平方根，如任意大于平方根的除数将有一个低于平方根的相应除数。
• 如果计数可被任何 x 整除，则 isprime 标志设置为 False 并且内部循环中断。
• 如果未找到约数，则计数为素数并打印。

高级素数生成：

为了更有效地生成素数，埃拉托斯特尼筛法推荐。这是一个带注释的优化 Python 实现：

def gen_primes():
    D = {}
    q = 2
    while True:
        if q not in D:
            yield q
            for later in range(q * q, 1000000, q):
                D[later] = [q]
        else:
            for later in range(q + D[q][0], 1000000, q):
                D.setdefault(later, []).append(q)
            del D[q]
        q += 1

以上是如何在 Python 中优化简单的素数生成器？的详细内容。更多信息请关注PHP中文网其他相关文章！