At the risk of doing someone's homework...
A naive solution is to do trial division by all integers from 2 up to sqrt
n.
{-
isPrime :: Integer -> BoolisPrime n
| n < 2 = False
| otherwise = f 2 n
where f k n
= if k > isqrt
then True
else undefined -- exercise for the reader
-}
and where
isqrt n returns floor (sqrt n)
Here, f is the helper function, and is only in scope inside the definition
of isPrime. This is a common haskell idiom- a helper function that is not
quite general purpose enough to be made a standalone function can be defined
"on the fly" and doesn't need a name or type signature.
You could fancy this up to make it more efficient. I've also seen
probabilistic functions that can handle huge numbers, but I can't remember
if they are recursive.
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
