Determining if a given number is prime in haskell

Question

Therefore, I developed the following function to determine if a given number is a prime in Haskell (assuming the first prime is 2):

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

it has an obvious trap of continuing the evaluation, even if it is divided into several numbers :(. Is there any sane way to “cut” the evaluation when it finds more than one solution using list expressions?

Also, what other implementations would you try on? I'm not looking for performance here, I'm just trying to figure out if there are other, more "modest" ways to do the same.

Answer 1

A quick change in your code that will “shorten” the grade and rely on Haskell's laziness:

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

The very first k divider will cause the list to be non-empty, and the null implementation on Haskell will only consider the first element of the list.

You only need to check before 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 want to conduct high-performance simplicity testing, it is preferable to use a library.

Answer 2

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

and here is prime.hs github project

Answer 3

Perhaps this is not directly related, but on the topic of searching for primes in functional languages, I found Melissa E. O'Neill The original sieve of Eratosthenes is very interesting.

Answer 4

Ignoring the problem with spaces and focusing on a narrow point of a more efficient method 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 

Answer 5

I like this approach:

First make a function to get all factors n:

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

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

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