确定给定数字是否是Haskell中的质数 [英] Determining if a given number is a prime in haskell

问题描述

因此，我设计了以下函数来查看给定数字是否是Haskell中的质数（假定第一个质数为2）：

So I have devised the following function for seeing if a given number is a prime in Haskell (it assumes the first prime is 2):

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

即使可以被多个数整除，它仍然具有继续进行评估的明显陷阱:(。当找到多个解决方案时，是否有任何 sane 方法削减评估，使用列表

it has the obvious pitfall of continuing the evaluation even if it is divisible by several numbers :(. Is there any sane way of "cutting" the evaluation when it finds more than one solution, using list comprehensions?

还可以尝试其他实现吗？我不是在这里寻找性能，我只是想看看是否还有其他的实现？

Also, which other implementations would you you try on? I'm not looking for performance here, I'm just trying to see if there are other more "haskellish" ways of doing the same thing.

推荐答案

对代码的快速更改将缩短评估，并且

A quick change to your code that will 'short circuit' the evaluation, and relies on the laziness of Haskell Lists, is:

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

k 的第一个除数将导致列表为非空，而 null 的Haskell实现将仅看看列表的第一个元素。

The very first divisor of k will cause the list to be non-empty, and the Haskell implementation of null will only look at the first element of the list.

您只需要最多检查 sqrt （k） 但是：

You should only need to check up to sqrt(k) however:

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

当然，如果您要进行高性能的素数测试，则首选库。

Of course, if you are looking to do high-performance primality testing, a library is preferred.

这篇关于确定给定数字是否是Haskell中的质数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！