[Haskell-cafe] Writing a function isPrime using recursion.
Nathan Bloomfield
nbloomf at gmail.com
Thu Oct 16 00:59:14 EDT 2008
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.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.haskell.org/pipermail/haskell-cafe/attachments/20081015/18171eb9/attachment.htm
More information about the Haskell-Cafe
mailing list