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.