如何加速质数查找过程？

Question

我在处理欧拉计划的第七个问题时遇到了问题。我的代码运行时间太长了。以下是我的代码：

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()

如何使它更快？还有其他方法吗？

- smid_the_best

---

这是Python2.x还是Python3.x？对于Python2.x，一个非常快的优化方法是从range切换到xrange。 - mgilson

这个实现中有几个地方不太合理：(1) 寻找因子时，可以在被测试的数的平方根处停止。如果大于平方根的任何数都是因子，那么一定存在相应较小的因子。(2) 一旦找到一个因子，就退出循环（即使用break）。为什么要在找到后继续寻找呢？(3)你只需要测试2作为偶数的因子。之后，可以跳过所有偶数。还有其他加速的方法，但我列出的这些是非常微不足道的。 - Tom Karzes

为了提高速度，使用更高效的算法，例如埃拉托斯特尼筛法。对于大质数，通过将每个数字除以它之前的所有数字来计算会花费很长时间。 - Akshat Mahajan

Answer 1

您应该让自己变得更容易并在结尾打印素数计数，这就是我怀疑p变量存储的内容。

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

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

2：在除数小于或等于平方根且prime == True时测试除数。

3：如果仍不是素数，则增加2，以便仅测试奇数(所有偶数都已通过num % 2检查)。

如果您想变得超级高效，每个不是素数的数字都至少有一个素因子，因此您可以将找到的每个素数存储在数组中，并仅检查其中最高的...但这是很多额外编码对此问题不必要。使用上述逻辑，在测试运行中几秒钟内找到了前10000个素数。

如果您考虑数字100，则您的逻辑会测试99个可能的除数。上述逻辑仅测试2然后停止。最坏情况是去平方根只需要5次计算，分别为2,3,5,7,9...，而不是99次。

- Lost

Answer 2

我使用以下方法来检查数字是否为质数（运行时间为0m0.612s）：

import math

def is_prime(num):
    if num == 0 or num == 1:
        return False
    if num == 2:
        return True
    temp = 2
    while temp < math.sqrt(num) + 1:
        if num % temp == 0:
            return False
        temp += 1

    return True

- Alex L