Déterminer si un nombre donné est premier en haskell

J'ai donc imaginé la fonction suivante pour voir si un nombre donné est premier en Haskell (il suppose que la première prime est de 2):

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

il a, de toute évidence piège de la poursuite de l'évaluation, même si elle est divisible par plusieurs numéros :(. Est-il sane façon de "couper" l'évaluation lorsqu'il trouve plus d'une solution, en utilisant la liste des compréhensions?

Aussi, d'autres implémentations voulez-vous vous essayer? Je ne suis pas à la recherche de la performance ici, j'essaie juste de voir si il y a d'autres plus "haskellish" façons de faire la même chose.

double possible de Paresseux Liste des Nombres premiers

OriginalL'auteur devoured elysium | 2011-01-14

  1. 22

    Un changement rapide de votre code qui permettra de "court-circuit" de l'évaluation et s'appuie sur la paresse de Haskell Listes:

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

    Le premier diviseur de k sera la cause de la liste non vide, et le Haskell mise en œuvre de null ne regarder que le premier élément de la liste.

    Vous aurez uniquement besoin de vérifier jusqu'à sqrt(k) or [1]:

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

    Bien sûr, si vous êtes à la recherche à la haute performance des tests de primalité, une bibliothèque est préféré.

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

    OriginalL'auteur tildedave

  2. 10

    Ici est la meilleure ressource pour les nombres premiers en haskell dans haskell.org

    et ici le premier.hs projet github

    OriginalL'auteur

  3. 6

    C'est peut-être pas directement pertinente, mais sur le sujet de trouver des nombres premiers dans les langages fonctionnels, j'ai trouvé Melissa E. O'Neill La Véritable Crible d'Eratosthène très intéressant.

    OriginalL'auteur gspr

  4. 4

    Ignorant les premiers à la question, et en se concentrant sur l'étroit point d'une méthode plus efficace de 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

    OriginalL'auteur dave4420

  5. 4

    J'aime cette approche:

    D'abord faire la fonction pour obtenir tous les facteurs de n:

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

    Ensuite vérifier si les facteurs ne sont que le nombre donné et 1, le cas échéant, le nombre est premier:

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

    OriginalL'auteur notgiorgi