Haskell Prime 测试混淆

所以我对 Haskell 完全陌生，希望它不会显示太多。无论如何，我试图创建一个函数来确定一个数字是否为素数。基本思想是这样的:给定一个数，看看它是否能被任何小于它的数整除。如果是，则返回 false。如果不是，则为素数，返回 true。到目前为止的代码(已知可以工作)是这样的:

divisible :: Integer -> Integer -> Bool
divisible x 2 = even x
divisible x y = ((x `mod` y) /= 0) && not (divisible x (y-1))
isPrime :: Integer -> Bool
isPrime x = not (even x) && not (divisible x (x-1))

产生:

ghci> isPrime 9
False
ghci> isPrime 13
True

我想做的是稍微优化一下，因为我只需要检查小于或等于 sqrt(x) 的值。问题是，当我尝试实现这一点时，事情变得疯狂:

isPrime x = not (even x) && not (divisible x (ceiling(sqrt(fromIntegral(x-1)))))

除了它看起来很糟糕(我说我是新人)之外，它还没有给出正确的结果:

ghci> isPrime 9
False
ghci> isPrime 13
False

我试图弄清楚发生了什么变化，因为:

ghci> ceiling(sqrt(13))
4

似乎给了我正确的号码。我知道这是一个小问题，但我很困惑......

最佳答案

你把你的条件搞混了:

divisible x y = ((x `mod` y) /= 0) && not (divisible x (y-1))

应该

divisible x y = (x `mod` y) == 0 || divisible x (y-1)

为了测试工作。

按原样，您的 divisible 函数会扩展，例如

divisible 21 5 = (21 `mod` 5 /= 0) && not (divisible 21 4)
               = (21 `mod` 5 /= 0) && not ((21 `mod` 4 /= 0) && not (divisible 21 3))
               = not ((21 `mod` 4 /= 0) && not ((21 `mod` 3 /= 0) && not (divisible 21 2)))
               = not (True && not (False && not (divisible 21 3)))
               = not (not False)
               = False

由于 21 `mod` 3 == 0 和 isPrime 21 计算为 True 的平方根界限。

但是，我得到

*StrangePrime> isPrime 9
True
*StrangePrime> isPrime 13
True

使用平方根的代码。

没有平方根，它碰巧适用于奇数，因为奇合数与其任何除数之间的差总是偶数。对 divisible 展开 n = p*m 几步，其中 p 是奇数复合 n 的最小素因数，我们看到

divisible n (n-1) = n `mod` (n-1) /= 0 && not (divisible n (n-2))
                  = not (divisible n (n-2))
                  = not (n `mod` (n-2) /= 0 && not (divisible n (n-3)))
                  = not (not (divisible n (n-3)))
                  = not^2 (divisible n (n-3))

并归纳地

divisible n (n-1) = not^(k-1) (divisible n (n-k))

如果没有大于 n 的 n-k 的除数。现在，在上述情况下， n 的最大除数是 m = n - (p-1)*m ，所以我们得到

divisible n (n-1) = not^((p-1)*m-1) (divisible n m)
                  = not^((p-1)*m-1) (n `mod` m /= 0 && not (...))

但是 n `mod` m == 0 ，所以我们有

divisible n (n-1) = not^((p-1)*m-1) False

由于 p 是奇数， p-1 是偶数，因此 (p-1)*m 也是偶数，所以我们总共有奇数个 not ，它与一个 not 相同，给出

divisible n (n-1) = True
isPrime n = not (even n) && not (divisible n (n-1)) = True && not True = False

如果 p 是奇素数，则展开到达 divisible p (p-1) = not^(p-3) (divisible p (p - (p-2))) 。 p-3 是偶数，divisible p 2 是 even p ，也就是 False 。

通常，将 divisible n s 视为奇数 n ，并让 d 为不超过 n 的 s 的最大除数，如果 n 是复合的，或者 d = 2 如果 n 是质数。 divisible n s 的展开还是一样的

divisible n s = not^k (divisible n (s-k))

虽然没有找到除数和 s-k > 2 。所以在复合 n 的情况下，我们发现

divisible n s = not^(s-d) (divisible n d)
              = not^(s-d) (n `mod` d /= 0 && not (...))
              = not^(s-d) False
              = odd (s-d)
              = even s     -- since d is odd, as a divisor of an odd number

在奇素数 n 的情况下，

divisible n s = not^(s-2) (divisible n 2)
              = not^(s-2) (even n)
              = not^(s-2) False
              = odd s

因此 divisible n s 测量 s 到 n 的下一个较小除数或到 2 的距离的奇偶性，以较大者为准。当 s 是 n-1 时，起点总是偶数，所以它计算正确，但 ceiling (sqrt (fromIntegral (n-1))) 可能是奇数，在这种情况下，结果被翻转，复合被声明为素数，反之亦然。

如果您确保第一个调用获得偶数第二个参数(因此，如果 divisible 为奇数，则从 ceiling (sqrt (fromIntegral (n-1))) 开始)，您可以使 ceiling (sqrt (fromIntegral (n-1))) + 1 函数用于具有平方根界限的奇数的素性测试，但该函数的逻辑令人困惑，它的名称没有正确描述其结果。

一种更惯用的写法是

isPrime n = and [n `mod` k /= 0 | k <- [2 .. ceiling (sqrt $ fromIntegral n)]]

当跳过先前测试中已知为非因数的候选除数时，测试变得更有效，简单的是跳过除 2 以外的所有偶数，

isPrime 2 = True
isPrime n = all ((/= 0) . (n `mod`)) (2 : [3, 5 .. ceiling (sqrt (fromIntegral n))])

稍微多一点，但更有效的是跳过 3 的倍数

isPrime n = all ((/= 0) . (n `mod`)) (takeWhile (<= bound) (2:3:scanl (+) 5 (cycle [2,4])))
  where
    bound = ceiling (sqrt (fromIntegral (n-1)))

同样，可以从试除数中消除更多小素数的倍数，每个都获得一点效率，但代价是更复杂的轮子，例如还消除了 5 的倍数导致

isPrime n = all ((/= 0) . (n `mod`)) (takeWhile (<= bound) (2:3:5: scanl (+) 7 (cycle [4,2,4,2,4,6,2,6])))
  where
    bound = ceiling (sqrt (fromIntegral (n-1)))

关于Haskell Prime 测试混淆，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/11019453/