Project Euler 10编译缓慢

Question

我是新手。我在试欧拉问题库档案的第十个问题。我的代码看起来不错，但效率不高。我不确定，我怎么能这么快。我的代码如下。

def isPrimeNum(num):
    for i in range(2, num):
        if num % i == 0:
            return False
    return True
def main():
    listOfPrimes = []
    sum = 0
    upperLim = 2000000
    for i in range(2, upperLim):
        if isPrimeNum(i) == True:
            sum += i
        else:
            continue
main()

Answer 1

在isPrimeNum函数中检查数字是否为素数时，请使用for i in range(2, int(num ** .5) + 1)，而不是当前版本的for循环。它之所以有效，是因为n的所有唯一除数都是小于或等于sqrt(n(的数字。检查"；原始性测试"；维基百科上的文章。

有了这个修改，你将获得显著的加速。我的机器上的结果：

# old version
%timeit main(20_000)
1.36 s ± 2.83 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
# new version
%timeit main(20_000)
26.5 ms ± 79.6 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)