python之性能之为什么具有范围的素数生成算法比使用素数列表快得多

我写了两段结构几乎相同的代码，

def prime_gen1(Limit = 10000): 
    List = [2,] 
    for x in range(3,Limit): 
        for y in List: 
            if not x%y: 
                break 
        if not x%y: 
            continue 
        else: 
            List.append(x) 
            yield x 
 
def prime_gen2(Limit = 10000): 
    from math import floor 
    for x in range(3,Limit): 
        for y in range(2, floor(x**0.5)+2): 
            if not x%y: 
                break 
        if not x%y: 
            continue 
        else: 
            yield x 
 
>>> list(prime_gen1(20000)) == list(prime_gen2(20000)) 
True 
>>> def time1(number): 
    st = time() 
    list(prime_gen1(number)) 
    end = time() 
    return end - st 
 
>>> def time2(number): 
    st = time() 
    list(prime_gen2(number)) 
    end = time() 
    return end - st 

一个与另一个做同样的工作，但后者实际上工作得更快。我想知道为什么会这样。

逻辑上 - 或非逻辑上，我认为用质数检查会胜过其他方式，在这种情况下 - 检查 3 和数字根之间的数字。但时间检查反之亦然，检查所有数字工作得更快 -大约5次。 它的性能越来越不同，

>>> time1(200000) 
8.185129404067993 
>>> time2(200000) 
0.4998643398284912 

第二种方法是超越它。这有什么不同？

请您参考如下方法:

列表版本比只对数字的平方根进行更多检查

对于 200000 的限制，平方根是 ~447 小于200000的质数有17983个

只需添加您执行 x%y 检查的次数即可

def prime_gen1(Limit = 10000): 
    List = [2,] 
    modulo_checks = 0 
    for x in range(3,Limit): 
        for y in List: 
            modulo_checks += 1 
            if not x%y: 
                break 
        if not x%y: 
            continue 
        else: 
            List.append(x) 
            yield x 
    print(modulo_checks) 
 
def prime_gen2(Limit = 10000): 
    from math import floor 
    modulo_checks = 0 
    for x in range(3,Limit): 
        for y in range(2, floor(x**0.5)+2): 
            modulo_checks += 1 
            if not x%y: 
                break 
        if not x%y: 
            continue 
        else: 
            yield x 
    print(modulo_checks) 

现在对于限制 200000，版本 1 执行 162416226 次检查，第二个执行 7185445

如果您为列表循环添加一个早期中断，列表版本会明显更快(1799767 检查 0.24 秒与 7185445 检查 0.64 秒相比快 2 倍)

... 
    sq_root = floor(x ** 0.5) + 2 
    for y in List: 
        modulo_checks += 1 
        if not x % y or y > sq_root: 
            break 
... 

如果你想比较算法速度，移除数学导入