python - 为什么这会使我的素数生成算法花费更长的时间？

Question

我试图找到 1 000 000 以下的所有素数。因为所有非素数都可以分解为素数，所以我的方法是从 [2, 3] 开始我的素数列表，然后遍历每个数字直到1 000 000。如果一个数字可以被 prime_list 中的任何数字整除，那么它就不是素数，我将移至下一个数字。如果这个数字不能被 prime_list 中的任何数字整除，那么它一定是素数，并且它被添加到这个列表中。

为了尝试提高效率，我添加了一个语句来仅检查所讨论的数字是否可以被低于该数字平方根的值整除。我认为这会减少很多计算时间，但实际上它使我的程序花费更长的时间。谁能解释一下为什么？

这是我的代码:

import math

import time
start_time = time.time()

prime = [2, 3]

def prime_checker(a):
    for j in prime:
        if j < (int(math.sqrt(a)) +1 ):     /// without this line, the program runs faster
            if a % j == 0:
                return False

for i in range (2, 100000):
    if prime_checker(i) != False:
        prime.append(i)

print prime[-1]

print "Time taken = ", time.time() - start_time 

Answer 1

要进一步加快您的算法，请注意 2 是唯一的偶素数。所有其他偶数都是合数。你已经有了 prime = [2, 3] 所以你可以从 5 开始搜索(4 不是素数)并且只检查奇数:

for i in range (5, 100000, 2):
    if prime_checker(i) != False:
        prime.append(i)