python - 为什么程序需要这么长时间才能运行？

Question

我正在尝试使用 Python 解决来自 Project Euler 的问题。当 j 的范围很大时，为什么我的代码需要这么长时间才能运行。当 j 的范围很小时，它工作得很好。

标签： python

Answer 1

由于您的程序有 2 个完全迭代的 for 循环，因此您的程序时间复杂度为 O(n**2)，因此预计需要很长时间，您可以在代码中进行一些优化：

import math

def is_prime(number):
    for i in range(2, int(math.sqrt(number) + 1)):               
       if (number % i) == 0: 
           return False
    return True