Determining if a given number is a prime in haskell

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

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

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.

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.

Here is the best resource for prime numbers in haskell in haskell.org

and here prime.hs github project

I like this approach:

First make function to get all factors of n:

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

Then check if factors are only the given number and 1, if so, the number is prime:

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

It's perhaps not directly relevant, but on the topic of finding primes in functional languages I found Melissa E. O'Neill's The Genuine Sieve of Eratosthenes very interesting.

Ignoring the primes issue, and focusing on the narrow point of a more efficient method of 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

This may be silly and inefficient (I'm a complete Haskell newby), but the function isMyNumberPrime (in ghci) seems to tell you if a number is prime or not.

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