所以我设计了以下函数来查看给定数字是否是 Haskell 中的素数（它假设第一个素数是 2）：
isPrime k = length [ x | x <- [2..k], k `mod` x == 0] == 1
即使它可以被几个数字整除，它也有继续评估的明显缺陷:(。当它使用列表推导找到多个解决方案时，是否有任何理智的方法可以“削减”评估？
另外，您会尝试哪些其他实现？我不是在这里寻找性能，我只是想看看是否还有其他更“haskellish”的方式来做同样的事情。
问问题
33159 次
6 回答
31
对您的代码的快速更改将“短路”评估，并依赖于 Haskell 列表的惰性，是：
isPrime k = if k > 1 then null [ x | x <- [2..k - 1], k `mod` x == 0] else False
的第一个除数k将导致列表非空，而 Haskell 的实现null将只查看列表的第一个元素。
但是，您应该只需要检查sqrt(k)：
isPrime k = if k > 1 then null [ x | x <- [2..isqrt k], k `mod` x == 0] else False
当然，如果您希望进行高性能素性测试，则首选库。
于 2011-01-14T19:19:57.760 回答
12
这是haskell.org中haskell中素数的最佳资源
这里是prime.hs github项目
于 2011-01-14T12:07:57.670 回答
7
这可能不是直接相关的，但是关于在函数式语言中寻找素数的话题，我发现 Melissa E. O'Neill 的The Genuine Sieve of Eratosthenes非常有趣。
于 2011-01-14T12:00:07.223 回答
6
我喜欢这种方法：
首先制作函数以获取 n 的所有因数：
factors n = [x | x <- [1..n], mod n x == 0]
然后检查因子是否只是给定的数字和 1，如果是，则该数字是素数：
prime n = factors n == [1,n]
于 2016-05-09T18:46:07.083 回答
4
忽略素数问题，并专注于更有效方法的窄点length xs == n：
hasLength :: Integral count => [a] -> count -> Bool
_ `hasLength` n | n < 0 = False
[] `hasLength` n = n == 0
(_ : xs) `hasLength` n = xs `hasLength` (pred n)
isPrime k = [ x | x <- [2..k], k `mod` x == 0)] `hasLength` 1
于 2011-01-14T12:34:27.070 回答
0
这可能是愚蠢和低效的（我是一个完整的 Haskell 新手），但函数 isMyNumberPrime （在 ghci 中）似乎告诉你一个数字是否是素数。
factors n = [x | x <- [2..(n`div` 2)], mod n x == 0]
factormap n = fmap factors $ factors n
isMyNumberPrime n = case factormap n of [] -> True; _ -> False
于 2021-03-26T19:33:31.190 回答