两个非常相似的代码生成 n 下的素数但 CPU 时间非常不同

Question

这两个非常相似的代码具有非常不同的速度。我不明白为什么。第一个（2 分钟）比第二个（5 秒）慢得多。

from numpy import sqrt 
primes = [2]
for i in range(3, 1000000):
    sq = int(sqrt(i))
    aux = False
    for j in primes:
        if j>sq:
            aux = True
        elif i%j==0:
            break
    if aux:
        primes.append(i)

============================================= =====================

def isPrime(p, primes):
        bound = numpy.sqrt(p)
        i = 0
        while(primes[i] <= bound):
            if p % primes[i] == 0:
                return False
            i += 1
        return True

def compute_primes(bound):
    primes = []
    primes.append(2)
    for n in range(3, bound):
        answer = isPrime(n, primes)
        if answer:
            primes.append(n)
    return primes

compute_primes(1000000)

Answer 1

性能差异的原因是第一个版本在达到上限时不会像第二个版本那样中断内部循环。假设这两个版本都在检查 11 是否为素数。第一个版本将运行所有较小素数的内循环 (2, 3, 5, 7)，而第二个版本将仅检查小于或等于 sqrt(11) 的值：(2, 3)。

如果您将第一个版本更改为在达到上限时中断，它们运行大致在同一时间：

if j > sq:
    aux = True
    break

两个非常相似的代码生成 n 下的素数但 CPU 时间非常不同

Two very similar codes to generate the primes under n but very different CPU time

python

primes

time-complexity