4

我找到了这个 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
4

2 回答 2

10

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

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。由于它们都是素数，因此True如果n等于其中一个，该函数将返回。

接下来，该函数测试是否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 会更快。

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

在while循环中，如果n能被 整除i，则它不是素数，函数返回False。如果不是，i则由 "incrementer" 递增w，这同样更快。

也许该函数最棘手的部分在于倒数第二行：w = 6 - w. 这会导致“增量器”w在每次通过循环时在值 2 和 4 之间切换。在 4 的情况下w，我们绕过了一个可被 3 整除的数字。这比保持为 2 更快，因为该函数已经测试了可被 2 和 3 整除的能力。

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

于 2013-08-08T05:59:03.270 回答
3

除 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 中有一些非素数。

于 2013-08-08T06:01:07.500 回答