Tired Friday Haskell prime components

Ugh, such a busy week. Brain cells are dead, inside is a black stingy dirty mud. Rotten classes and filthy mediator patterns. Chara·cters in UTF16 and bits in little endian. To avoid any kind of human interaction and the even slight chance of bs-ing I decided to turn to my old friend, Euler.


It's novice problem, don't expect me any more complex:

The prime factors of 13195 are 5, 7, 13 and 29.
What is the largest prime factor of the number 600851475143 ?

I've implemented in some languages already, now time to see it in Haskell. Quickly installed the Haskell compiler and started refreshing my functional memories.

The problem is about prime components. Such a brilliant example to produce some horribly lazy slow algorithm in O(log * n²). I thought we should approach the problem with 2 functions - one to get the component and one to get the maximum item of it.

Fining prime component is not easy if you want to be effective. I also chose the lazy way. The signature will be the following:

prime_components :: (Integral a, Ord a) => a -> a -> [a]

We need to use Integral because we use integer arithmetics. Also it has to be Ord in order to compare. Why 2 arguments (I know it's always one in Haskell, but still, come on)? We pass the number in query and the current test modulo value. We refine stepwise the number and collect all prime tags. Easiest first case when the number itself is equal or greater then our test modulo. In that case we return the modulo as the only prime:

prime_components num a | num <= a = [num]

Don't be confused by the less then sign. It's gonna be equal, trust me. The next possible case is when the modulo divides the number exactly. In that case we subtract the number and start with a new modulo:

prime_components num a | num `mod` a == 0 = [a] ++ prime_components (num `quot` a) 2

Here we're using `quot` in order to work with Integral type values. All right, if number is greater than modulo but doesn't divide it exactly then we increment the modulo:

prime_components num a | otherwise = prime_components num (a + 1)

Woot, done. In one piece:

prime_components :: (Integral a, Ord a) => a -> a -> [a]
prime_components num a | num <= a = [num]
prime_components num a | num `mod` a == 0 = [a] ++ prime_components (num `quot` a) 2
prime_components num a | otherwise = prime_components num (a + 1)

(Haha, just randomly wanted to show an example and found a prime: 3982549, lovely) If you load this module and try you can see how it works:

*Main> prime_components 39824540 2
[2,2,5,7,17,29,577]

The exercise requires the largest prime, so our runner of the Euler problem needs to select the last item:

euler3 :: (Integral a, Ord a) => a -> a
euler3 a = last (prime_components a 2)

Sleep well.

---

Peter