使用平方根法求素数

Question

我能够使用这种方式为素数编写一个函数

def isprime(num):
    if num > 1:
        for i in range(2, num):
            if num % i == 0:
                return False
        return True

%timeit [i for i in range(1000) if isprime(i)]
7.94 ms ± 273 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)

然后我发现有一种使用平方根来写这个的更快的方法，但我无法理解它的工作原理。任何人都可以用更简单的术语解释这段代码以及它为什么有效？

def isprime(num):
    if num > 1:
        for i in range(2, int(num ** 0.5) + 1):
            if num % i == 0:
                return False
        return True

%timeit [i for i in range(1000) if isprime(i)]    
1.94 ms ± 54.7 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)

如果这是重复的请告诉我我会立即删除它。

Answer 1

这最好通过例子来解释。假设您想知道 143 是否为质数。你真的需要尝试除以 142、141、140、139 等等吗？显然，这些都没有除以 143；他们太大了。

但请看：

• 143 % 2 == 1
• 143 % 3 == 2
• 143 % 5 == 3
• 143 % 7 == 3
• 143 % 11 == 0

显然，11 除以 143。不是质数。

现在让我们试试 145。145 是质数吗？

• 145 % 2 == 1
• 145 % 3 == 1
• 145 % 5 == 0

显然，5 除以 145。不是质数。现在考虑，我们可以尝试

• 145% 29 == 0

这会起作用，因为 145 == 5*29，但没有必要尝试像 29 这样大的因数。 5 就足够了。

所以想想这个。如果合数 n == a*b 有两个因数 a 和 b，假设 b > sqrt(n)。在那种情况下，一定是 a < sqrt(n)，因为如果不是这样，那么 a*b 就不能等于 n。事实上，如果不是这样，那么 a*b 将大于n，这意味着 a*b 不是 n 的适当分解。

您需要做的就是找到较小因子的值。较小的因子小于或至多等于平方根。如果没有找到小于或等于平方根的因数，则可以得出所研究的数是素数。