[Haskell-cafe] Writing a function isPrime using recursion.

[Nathan Bloomfield]

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