确定给定数字是否是haskell中的素数

Question

所以我设计了以下函数来查看给定数字是否是Haskell中的素数(它假设第一个素数是2):

isPrime k = length [ x | x <- [2..k], k `mod` x == 0] == 1

它有继续评估的明显缺陷,即使它可被几个数字整除:(.当使用列表推导找到多个解决方案时,是否有任何理智的"削减"评估的方法？

另外,你会尝试哪些其他实现？我不是在这里寻找表现,我只是想看看是否还有其他更"冒险"的方式来做同样的事情.

Answer 1

快速更改代码,使评估"短路"并依赖于Haskell列表的懒惰:

isPrime k = if k > 1 then null [ x | x <- [2..k - 1], k `mod` x == 0] else False

第一个除数k将导致列表非空,而Haskell实现null只会查看列表的第一个元素.

你应该只需要检查sqrt(k)然而[1]:

isPrime k = if k > 1 then null [ x | x <- [2..isqrt k], k `mod` x == 0] else False

当然,如果您希望进行高性能素性测试,则首选库.

[1] http://www.codecodex.com/wiki/Calculate_an_integer_square_root#Haskell

Answer 2

这是haskell.org 中haskell素数的最佳资源

这里是prime.hs github项目

Answer 3

它可能不是直接相关的,但是关于在函数式语言中找到素数的主题,我发现Melissa E. O'Neill的Eratosthenes的真正筛子非常有趣.

Answer 4

我喜欢这种方法：

首先使用 make 函数获取 n 的所有因数：

factors n = [x | x <- [1..n], mod n x == 0]

然后检查因子是否只是给定的数字和 1，如果是，则该数字是质数：

prime n = factors n == [1,n]