3

所以我对 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

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

4

2 回答 2

13

你把你的条件搞混了：

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哪里pn

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所以是偶数，所以 s 也是(p-1)*m，所以我们总共有奇数个nots，与一个 相同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

因此测量到下一个较小除数或到 2divisible n s的距离的奇偶性，以较大者为准。什么时候，起点总是偶数，所以它计算正确，但可能是奇数，在这种情况下，结果被翻转并且复合被声明为素数，反之亦然。snsn-1ceiling (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)))
于 2012-06-13T16:47:46.920 回答
2

这是我的做法： 

divisibleBy :: (Integral a) => a -> a -> Bool
divisibleBy x y = mod x y == 0

isPrime :: (Integral a) => a -> Bool
isPrime x = or $ map (divisibleBy x) [2..(x-1)]

divisibleBy是一个简单的可分性测试。isPrime对 1 和 x 之间的所有整数执行此测试，如果x可被任何这些整数整除，则返回 true。您可以将上限更改为 root x，就像您在代码中所做的那样，但除此之外这是可行的。

于 2012-06-13T16:51:03.487 回答