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

Question

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

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

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

Answer 1

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

对于 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
...

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