为什么这个素数测试有效？

Question

我找到了这个Python函数，用于测试一个数字是否为质数；然而，我无法弄清楚算法的工作原理。

def isprime(n):
   """Returns True if n is prime"""
   if n == 2: return True
   if n == 3: return True
   if n % 2 == 0: return False
   if n % 3 == 0: return False

   i = 5
   w = 2
   while i * i <= n:
      if n % i == 0:
         return False

      i += w
      w = 6 - w

   return True

- user2640586

Answer 1

让我们从函数代码的前四行开始：

def isprime(n):
    if n == 2: return True
    if n == 3: return True
    if n % 2 == 0: return False
    if n % 3 == 0: return False

这个函数首先测试n是否等于2或3。由于它们都是素数，如果n等于其中任何一个，该函数将返回True。

接下来，该函数测试n是否可被2或3整除，并在任一条件为真时返回False。这消除了大量的情况，因为所有大于2的数字中有一半不是素数-它们可以被2整除。同样的原因适用于测试可否被3整除-这也消除了大量情况。

该函数更复杂的部分在接下来的几行中：

i = 5
w = 2
while i * i <= n:
    if n % i == 0:
        return False

    i += w
    w = 6 - w

return True

首先，i （或索引）被设置为5。2和3已经被测试过了，4则是通过 n％2 进行测试的。所以从5开始是有意义的。

接下来，w 被设置为2。w似乎是一个“增量器”。到目前为止，函数已经测试了所有偶数（n％2），因此增加2会更快。

该函数进入一个带有条件 i * i <= n 的 while 循环中。使用这个测试是因为每个合数都有一个小于或等于它平方根的适当因子。在平方根之后测试数字是没有意义的，因为那将是多余的。

在 while 循环中，如果 n 可以被 i 整除，则其不是质数，函数返回 False。如果不能，则增加“增量器” w，这也更快。

函数最棘手的部分也许在倒数第二行：w = 6 - w。这使得“增量器” w 在每次循环中在值2和4之间切换。在 w 为4的情况下，我们可以跳过一个可被3整除的数字。这比保持在2更快，因为函数已经测试了2和3的可除性。

最后，该函数返回 True。如果函数没有检测到任何n可被除以某个数的情况，则它必须是一个质数。

- joshreesjones

Answer 2

除了2和3以外，所有的质数都可以用(6*n)+1或(6*n)-1表示，其中n是0到无穷大的数字。 这个程序就是根据这个思想来工作的。 使用这些代码行，可以检查数字是否可以被2或3整除。

 if n % 2 == 0: return False
 if n % 3 == 0: return False

然后我们需要检查该数字是否可以被大于3的其他质数整除。

i = 5
w = 2
while i * i <= n:
   if n % i == 0:
       return False

   i += w
   w = 6 - w

下一个质数是5，因此将i的初始值设置为5。 要获取集合中的所有数字（6*n）+1或（6*n）-1，可以交替更改w的值（2,4）。 此代码片段用于检查数字的平方根。

 while i * i <= n:

因为集合中包含了一些非质数的数字(6*n)+1或(6*n)-1，所以这段代码不够高效。

- mridul