在Haskell中确定给定的数字是否为质数

Question

所以我设计了以下的Haskell函数，用于判断给定的数字是否为素数（假设第一个素数为2）：

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

它显然有一个缺陷，即使它可以被多个数字整除，它仍然会继续计算 :(. 是否有任何“明智”的方法，在列表推导中找到多个解决方案时“切断”计算？

此外，您还尝试了哪些其他实现？我在这里不关注性能，只是想看看是否有其他更“Haskell式”的方式来完成相同的事情。

- devoured elysium

---

可能是质数的惰性列表的重复。 - Landei

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)：

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

当然，如果您想进行高性能素数测试，最好使用库。

- tildedave

---

@WillNess 这对你来说可能是毫无意义的，但对我来说不是，而且对其他人也不是，因为它还得到了另外两个人的批准。我经常在SE上编辑帖子，使它们更易读和易接近，并获得了批准。我所做的这些更改对你来说可能看起来毫无意义，但它们确实很重要。学习非常关键，信息应该尽可能地呈现。 - Can

@Can "再次"犯了两个错误（？据我所知，这是我们的第一次交流）。第一，您将isqrt更改为sqrt，这不适用于Integral类型，因此代码会引发错误。第二，您将“relies”更改为“rely”，这破坏了句子的含义（在某种微妙但真实的意义上）。 - Will Ness

@WillNess 无论如何，我不在意你是否已经撤销了我的编辑。然而，作为最后的声明，我想说，称呼其他人也支持的东西是荒谬的，这既很奇怪，更重要的是很粗鲁。请先问个为什么，养成习惯。 - Can

@Can，很不幸，你的编辑导致了我向你展示的两个问题。进行对话以澄清事情是好的。即使是你制作的工件受到批评，也不应该将其个人化。有关更多信息，请参见https://www.dreamsongs.com/10ideas.html。 - Will Ness

@WillNess 请放心，我绝对不会把它当成个人问题，只是陈述我的想法。确实，将 isqrt 更改为 sqrt（嘿，学到了新东西，谢谢）是一个错误，而且我在快速打字时错过了单词 rely，但这些并不是唯一的更改。无论如何，我真的不想再深入探讨了。谢谢。 - Can

Answer 2

这里是关于Haskell中质数的最佳资源，可以在haskell.org上找到。

此外，还有一个prime.hs的Github项目。

- user467871

Answer 3

我很喜欢这种方法：

首先编写一个函数来获取n的所有因数：

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

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

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

- notgiorgi

Answer 4

虽然这与直接相关的内容有些许不同，但在函数式编程语言中寻找质数方面，我发现Melissa E. O'Neill的《The Genuine Sieve of Eratosthenes》非常有趣。

- gspr

Answer 5

忽略质数问题，聚焦于更高效的方法来判断 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

- dave4420

Answer 6

这可能有些愚蠢和低效（我是一个完全的Haskell新手），但是在ghci中，函数isMyNumberPrime似乎可以告诉你一个数字是否为质数。

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

- DMJ

---

对于一个完全的Haskell新手来说还不错。我测试了一些小数字，它也能正常工作。但是，这到底是如何工作的呢？factors提供哪些因子？它似乎既不是质因数，也不是所有因子。例如，8的质因数是[2,2,2]，而因子是[1, 2, 4, 8] - 但是你的函数提供了不同的结果。下一个问题是为什么要使用map - 因子的因子？如果您不介意的话，请让我编辑您的帖子或者请解释得更好一些。谢谢。 - Jörg Brüggmann

因子可以通过 factors n = [ n' | n' <- [1..n], n \mod` n' == 0]` 进行评估。 - Jörg Brüggmann

质数是只有1和它本身作为因子的数字，因此 isPrime n = factors n == [1,n]。 - Jörg Brüggmann

代码 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对于数字1不起作用。1 不是质数，而isMyNumberPrime 1的结果却是True`。 - Jörg Brüggmann

谢谢你的评论，Jorg。不幸的是，我发布这个函数已经很久了，我完全忘记了它是如何工作的（也很多Haskell，说实话）。 - DMJ