采用6k±1形式筛选候选质数后，素数查找程序为何变慢？

原始素数筛选程序 #

number = int(input("Enter number: "))
prime_numbers = [2]  # First prime is needed.
for number_to_be_checked in range(3, number + 1):  
    square_root = number_to_be_checked ** 0.5
    for checker in prime_numbers:  # Checker will become 
           # every prime number below the 'number_to_be_checked'
           # variable because we are adding all the prime numbers 
           # in the 'prime_numbers' list.
        if checker > square_root:
            prime_numbers.append(number_to_be_checked)
            break
        elif number_to_be_checked % checker == 0:
            break
print(prime_numbers)

基于6k±1形式的候选数生成器 #

def potential_primes(number: int) -> int:
    """Generate the numbers potential to be prime"""
    # Prime numbers are always of the form 6k ± 1.
    number_for_function = number // 6
    for k in range(1, number_for_function + 1):
        yield 6*k - 1
        yield 6*k + 1

问题 #

已知除2、3外，素数均为6k±1的形式，理论上用这个生成器减少待检查数量后程序应该更快，但实际反而更慢，请问原因是什么？

原因分析 #

• 生成器的上下文切换开销：Python生成器每次yield都要进行上下文保存与恢复，这是额外的运行时开销。对比range这种底层C实现的迭代器，自定义生成器的迭代效率要低很多，当目标数值较大时，频繁yield的成本会抵消减少候选数带来的优势。
• range的底层优化优势：range是Python内置的高度优化对象，它不需要每次迭代都计算数值，内存占用也极小。而你的生成器每次迭代都要计算6*k-1和6*k+1，加上生成器本身的框架开销，整体迭代成本远高于range。
• 小数值场景的反向效果：当目标数值较小时，6k±1形式的候选数数量减少的幅度有限，此时生成器的额外开销占比更高，直接导致程序变慢。
• 未同步优化检查逻辑：如果你的优化版本只是替换了候选数生成方式，但检查逻辑（比如遍历所有已找到的素数到平方根）没有配合优化，那么减少候选数带来的收益会被不变的检查成本抵消，甚至因为生成器的开销而整体变慢。
• 额外边界处理成本：原程序天然覆盖了所有数，而使用生成器后需要额外处理2、3以及小于6的输入场景，这些分支逻辑会增加额外的运行时判断成本。

内容的提问来源于stack exchange，提问作者PythonBeginner