Ermitteln, ob eine gegebene Zahl eine Primzahl in Haskell ist

Question

So habe ich die folgende Funktion ausgedacht für zu sehen, ob eine gegebene Zahl eine Primzahl in Haskell (es nimmt die erste Primzahl 2): ​​

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

hat die offensichtliche Gefahr der Bewertung der fort auch wenn es durch mehrere Zahlen teilbar ist :(. gibt es eine sane Art und Weise von „Schneiden“ der Auswertung, wenn es mehr als eine Lösung findet, Listenkomprehensionen mit?

auch die andere Implementierungen würden Sie versuchen? Ich bin nicht auf der Suche nach Leistung hier, ich versuche nur zu sehen, ob dort sind andere "haskellische" Arten, dasselbe zu tun.

Answer 1

Es ist vielleicht nicht direkt relevant, aber zum Thema Primzahlen in funktionalen Sprachen fand ich Melissa E. O'Neill's The Genuine Sieve of Eratosthenes sehr interessant.

Answer 2

Hier ist Ihr kompetenter Partner für prime numbers in haskell in haskell.org

und hier prime.hs GitHub Projekt

Answer 3

die Primzahlen Problem zu ignorieren und auf der Engstelle eine effizientere Methode der length xs == n Fokussierung:

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

Eine schnelle Änderung an Ihrem Code, der die Auswertung "kurzschließt" und auf der Faulheit der Haskell-Listen beruht, lautet:

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

Der erste Teiler von k wird die Liste führt nicht leer und die Haskell Implementierung von null nur beim ersten Elemente der Liste aussehen zu sein.

Sie sollten nur sqrt (k) jedoch prüfen müssen [1]:

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

Natürlich, wenn Sie High-Performance-Primtests suchen zu tun, eine Bibliothek bevorzugt.

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

Answer 5

Ich mag diesen Ansatz:

Erste Schliesser alle Faktoren von n zu erhalten:

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

Dann überprüfen, ob Faktoren nur die gegebene Zahl sind und 1, wenn ja, ist die Zahl prime:

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