La determinación de si un número dado es primo en Haskell

Question

Así que han ideado la siguiente función para ver si un número dado es primo en Haskell (que asume el primer primer es 2):

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

Tiene la trampa obvia de continuar la evaluación, incluso si es divisible por varios números :(. ¿hay alguna cuerdo manera de "cortar" la evaluación cuando se encuentra más de una solución, usando listas por comprensión?

Además, el cual otras implementaciones ¿podrías probar? No estoy buscando rendimiento aquí, solo estoy tratando de ver si hay hay otras maneras más "haskellish" de hacer lo mismo.

Answer 1

Quizás no sea directamente relevante, pero en el tema de encontrar primos en lenguajes funcionales encontré muy interesante el The Genuine Sieve of Eratosthenes de Melissa E. O'Neill.

Answer 2

Aquí es el mejor recurso para prime numbers in haskell en haskell.org

y aquí prime.hs proyecto github

Answer 3

Haciendo caso omiso de la cuestión de los números primos, y se centra en la punta de un método más eficiente de length xs == n estrecha:

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 4

Un cambio rápido en su código que 'cortocircuitará' la evaluación y se basa en la pereza de las listas de Haskell es:

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

El primer divisor de k hará que la lista no esté vacía y la implementación de Haskell de null solo verá el primer elemento de la lista.

Sólo es necesario para comprobar hasta sqrt (k), sin embargo [1]:

isPrime k = null [ x | x <- [2..isqrt k], k `mod`x == 0] 

Por supuesto, si usted está buscando para hacer pruebas de primalidad de alto rendimiento, se prefiere una biblioteca.

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

Answer 5

me gusta este enfoque:

función primer lugar hacer para conseguir todos los factores de n:

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

a continuación, comprobar si los factores son sólo el número dado y 1, si es así, el número es primordial:

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