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:

\[
  \forall n \in \mathbb{N}
\]
\[
  p \left( n \right) = \left\{ \begin{array}{lr}
  0, & n = 1 \\
  1, & n = 2 \\
  0, & \text{$n$ is even} \\
  1, & \nexists m \in \left\{ x \in \mathbb{N} \, | \, 5 \leq x \leq{\sqrt{n}}, \text{$x$ is odd}  \right\}
  
\end{array} \right.
\]

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