Primzahlen in Haskell

prime.lhs

> module Main
>   where
> import Data.List

Entnimmt einer Liste solange ein Element, bis das Quadrat des Elementes über-
geben an die Funktion f False ergibt.

> takeWhileSquare :: Num a => (a -> Bool) -> [a] -> [a]
> takeWhileSquare f (x:xs)  | f (x^2)   = x:takeWhileSquare f xs
>                           | otherwise = []

Die Liste aller Prinzahlen auf dieser Welt, tut euch aber selbst einen gefallen
und ruft kein `last`, `tail` und ähnliches darauf auf, oder gar einfach nur 
ein stumpfes `primes`! `last` resultiert in einer endlosen Ausgabe von nichts
und der Rest in einer endlosen Ausgabe von ganz vielen Zahlen…

> primes :: Integral a => [a]
> primes = [ x | x <- [1..], isPrime x ]

Übergebt isPrime einfach eine Zahl, und isPrime erzählt euch, ob es sich um
eine Primzahl handelt.

> isPrime :: Integral a => a -> Bool
> isPrime 1 = False
> isPrime 2 = True
> isPrime n = not(or [ (n `mod` x) == 0 | x <- takeWhileSquare (<= n) primes ])

Liefert eine Liste mit allen Primzahlen kleinergleich n. Durch Verwendung von 
takeWhile wird die Liste primes so lange durchlaufen, bis das gelieferte Er-
gebnis angewendet auf (<= n) False ergibt. Dadurch wird diese Variante deutlich
schneller als meine erste, welche auch nach finden des letzten Elementes noch 
eine lange Zeit weiterlief. Diese Variante funktioniert allerdings nur bei
Listen, die entsprechend sortiert sind (hier aufsteigend!), ansonsten werden 
eventuell Elemente die zwar unter die Bedingung fallen aber erst nach einem
Element in der Liste stehen das nicht unter die Bedingung fällt, nicht mit in
das Ergebnis aufgenommen.

> primesUpTo :: Integral a => a -> [a]
> primesUpTo n = takeWhile (<= n) primes