haskellfunctional-programmingprimesprimality-test

Writing an isPrime function in Haskell


isPrime :: Int -> Bool
isPrime n = leastDivisor n == n

leastDivisor :: Int -> Int 
leastDivisor n = leastDivisorFrom 2 n

leastDivisorFrom :: Int -> Int -> Int
leastDivisorFrom k n | n `mod` k == 0 = k
                     | otherwise      = leastDivisorFrom (k + 1) n

My question would be:


Solution

  • It is too operational. It can be equivalently expressed(*) as

    isPrime :: Integer -> Bool
    isPrime n  =  [n] == take 1 [i | i <- [2..n], mod n i == 0]
    

    so it is more visually apparent and immediately clear, a one-liner easier to deal with.

    Trying it as

    GHCi> zipWith (-) =<< tail $ filter isPrime [2..]
    [1,2,2,4,2,4,2,4,6,2,6,4,2,4,6,6,2,6,4,2,6,4,6,8,4,2,4,2,4,14,4,6,2,10,2,6,6,4,6,6,2,10,2,4,2,12,12,
    4,2,4,6,2,10,6,6,6,2,6,4,2,10,14,4,2,4,14,6,10,2,4,6,8,6,6,4,6,8,4,8,10,2,10,2,6,4,6,8,4,2,4,12,8,4,
    8,4,6,12,2,18,6,10,6,6,2,6,10,6,6,2,6,6,4,2,12,10,2,4,6,6,2,12,4,6,8,10,8,10,8,6,6,4,8,6,4,8,4,14,10
    ......
    

    reveals how slow it is. We could try re-writing it as

    isPrime n  =  null [i | i <- [2..n-1], mod n i == 0]
               =  none (\ i -> mod n i==0) [2..n-1]
               =  all (\ i -> mod n i > 0) [2..n-1]
               =  and  [mod n i > 0 | i <- [2..n-1]]
    

    but [2..n-1] is not that much shorter than [2..n], isn't it. It should be much much shorter, ending much earlier than that; and even shorter still, with lots of holes in it...

    isPrime n = and [mod n p > 0 | p <- takeWhile (\p -> p^2 <= n) primes]
    primes = 2 : filter isPrime [3..]

    And the next improvement after that is, getting rid of mod altogether.


    (*) this expresses exactly the same computation action as your leastDivisor n == n is doing. take 1 takes just the first of the number's divisors, as a list; its length is necessarily 1; comparing it with the one-element list [n] is then equivalent to comparing the first - i.e. smallest - divisor with the number n. Just what your code is doing.

    But in this form, it is (arguably) a clearer code, more visually apparent. At least for me it is so. :)