python - 如何加快素数查找过程？

Question

我在做 Project Euler 的第 7 题时遇到了问题。我的代码需要很长时间才能完成。这是我的代码。

def Problem7():
    num = 0
    p = 0 
    while p < 10002 :
        prime = True
        for i in range(2,num):
            if (num%i==0):
                prime = False
        if prime:
           print(num)
           p = p + 1
        num = num + 1
Problem7()

如何让它更快？还有别的办法吗？

Answer 1

你应该让你的生活更轻松，并在末尾打印素数，我怀疑 p 变量正在存储。

如评论中所述，您可以使用更智能的算法来消除大量计算。

1:检查数字是否为偶数(num%2)(如果是，则不是素数)

2: 当除数小于或等于平方根和素数时 ==True，检验除数

3:如果仍然不是质数，则递增 2，这样您只测试奇数(所有偶数都用 num%2 检查)

如果您想获得 super 高效，每个非质数的数字都至少有一个质因数，因此您可以将找到的每个质数存储在一个数组中，并且只检查数组中最高的那些...但对于这个问题来说，有很多额外的编码是不必要的。使用上述逻辑，我在测试运行的几秒钟内找到了前 10,000 个素数。

如果您想到数字 100，您的逻辑会测试 99 个可能的除数。上面的逻辑只测试 2 然后停止。求平方根的最坏情况只有 2、3、5、7、9... 5 次计算，而不是 99 次。