在 Haskell 中编写 isPrime 函数

Question

isPrime :: Int -> Bool
isPrime n = leastDivisor n == n

leastDivisor :: Int -> Int 
leastDivisor n = leastDivisorFrom 2 n

leastDivisorFrom :: Int -> Int -> Int
leastDivisorFrom k n | n `mod` k == 0 = k
                     | otherwise      = leastDivisorFrom (k + 1) n

我的问题是：

• 这个功能有什么设计问题？

Answer 1

操作性太强了。可以等价地表示为^(*)为

isPrime :: Integer -> Bool
isPrime n  =  [n] == take 1 [i | i <- [2..n], mod n i == 0]

因此它在视觉上更加明显且立即清晰，“单行”更容易处理。 尝试一下

GHCi> zipWith (-) =<< tail $ filter isPrime [2..]
[1,2,2,4,2,4,2,4,6,2,6,4,2,4,6,6,2,6,4,2,6,4,6,8,4,2,4,2,4,14,4,6,2,10,2,6,6,4,6,6,2,10,2,4,2,12,12,
4,2,4,6,2,10,6,6,6,2,6,4,2,10,14,4,2,4,14,6,10,2,4,6,8,6,6,4,6,8,4,8,10,2,10,2,6,4,6,8,4,2,4,12,8,4,
8,4,6,12,2,18,6,10,6,6,2,6,10,6,6,2,6,6,4,2,12,10,2,4,6,6,2,12,4,6,8,10,8,10,8,6,6,4,8,6,4,8,4,14,10
......

揭示了它有多慢。我们可以尝试将其重写为

isPrime n  =  null [i | i <- [2..n-1], mod n i == 0]
           =  none (\ i -> mod n i==0) [2..n-1]
           =  all (\ i -> mod n i > 0) [2..n-1]
           =  and  [mod n i > 0 | i <- [2..n-1]]

但是 

[2..n-1]

并不

that

比 [2..n] 短很多，不是吗。它应该比那短得多

远

，结束得早远；甚至更短，里面有很多洞...

isPrime n = and [mod n p > 0 | p <- takeWhile (\p -> p^2 <= n) primes]

primes = 2 : filter isPrime [3..]

之后的下一个改进是，

完全摆脱

mod

。

---

(*) 这表示与您的

leastDivisor n == n ^{所做的计算操作完全相同。}

take 1

仅将数字的第一个除数作为列表；它的长度必然是1；将其与单元素列表

[n]

进行比较相当于将第一个（即最小）除数与数字

n

进行比较。正是您的代码正在做什么。

但在这种形式下，它（可以说）是更清晰的代码，更直观。至少对我来说是这样。 :)

Answer 2

我刚刚调整了之前的响应，这将复杂度从 O(n) 降低到了 O(sqrt n)，我认为<- [2..(floor (sqrt (fromIntegral n)))], mod n i == 0]