Euler Down

Euler, problem #3: What is the largest prime factor of the number 600851475143 ?

main = do {
  print (factors 1300); -- demonstrate factor lists
  print (last (factors 600851475143))
}

factors :: Integer -> [Integer]
factors num = factorise num 2


My solution is to produce a stream of factors, starting with the lowest. As you can see, I hand off from ‘factors num’ to ‘factorise num 2′. In order to test different factor values I need to include them (the factor values) in the method. I am using the value 2 (or ‘factor’ below) as a primitive state object. It only ever contains one value. It is incremented and passed down to further calls to factorise, and it is not returned. BUT it is definitely a state.

Before I would use multiple definitions for a method, with pattern matching to decide which definition would be used. The ‘pipe’ method below is the exact same thing, we just dont have to type ‘factorise num factor’ two extra times. And we don’t have to define num+factor for our conditionals. Also, the pipe visually associates all the definitions, making it more readable.

The matchers present a test – some pattern or condition – followed by a definition (stuff after the equals). The last matcher is the keyword ‘otherwise’, which will match all the leftovers.

factorise :: Integer -> Integer -> [Integer]
factorise num factor
  | factor > num = []
  | (mod num factor == 0) = factor : factorise (div num factor) factor
  | otherwise = factorise num (factor+1)


This method returns a list of integers. When the factor is greater than the num, it returns an empty list. When the factor moduloes to zero, then we put it in the front of the list, and try again. Finally, if the factor moduloes to non-zero, we need to try a different factor – so increment the current factor.

This is not an efficient method. The best improvement would be to replace the (factor+1) with something like ‘(nextPrime factor)’. We don’t need every single number, we should be able to skip just to the primes.

So I guess thats my next challenge, to create a state object that skips to the primes.

Advertisement