Thursday, March 21, 2013

Nieve Prime Finder in Haskell

To solve a cyber-dojo challenge (implement a function/method that returns the prime factors of a number) I decided to implement a somewhat nieve (but workable) isPrime function in Haskell. Here's the code:

-- Public type-definition
isPrime :: Integer -> Bool

-- Private type-definition
lookForPrimeFrom :: Integer -> Integer -> Bool

isPrime 2 = True
isPrime n
 | n < 2     = False
 | even n    = False
 | otherwise = lookForPrimeFrom n 5

lookForPrimeFrom n i
 | ceiling (sqrt (fromIntegral n))+1 < i   = True
 | (n `mod` i) == 0                        = False
 | otherwise                               = lookForPrimeFrom n (i+2)



This code (to me at least) seems very self-documenting. The more I'm playing around with Haskell, the more I'm enjoying it and seeing its strength as a functional language. I think if I were to map this algorithm into more mathematical notation it would look like:

nN

p(n)={0,n=11,n=20,n is even1,m{xN|5xn,x is odd}


As you can see, this is somewhat nieve; however, the Haskell code really is quite similar to the mathematical notation.

No comments:

Post a Comment