WARNING! This post contains a spoiler for Problem #3 listed at Project Euler. Do not read the rest of this post if you’re planning to attempt to solve the problem yourself.
Problem #3 in the series is the first one to bring in prime numbers. Here’s the question:
The prime factors of 13195 are 5, 7, 13 and 29.
What is the largest prime factor of the number 600851475143 ?
For this particular problem I decided to avoid generating prime numbers because that takes ages. I had a feeling that later on down the track I was going to encounter a problem where I would need to generate primes, but for this problem I didn’t find it necessary.
Instead, I attempted to use my noggin’. Up there for thinkin’, down there for dancin’. Here’s my Haskell source:
biggestDivisor :: Integer -> Integer biggestDivisor n | even n = biggestDivisor (div n 2) | otherwise = m n 3 where m n d | d >= n = d | mod n d == 0 = m (div n d) d | otherwise = m n (d + 2) main :: IO () main = print $ biggestDivisor 600851475143
Don’t ya just love built-in Big Integer support? 
This obviously works from the bottom up. It starts with a special case with an even number. It keeps dividing by two until it’s no longer even. At this point, it begins factorising using odd numbers starting at 3. The loop finishes when the last found factor is bigger than the number that is being factored. This works because as we find the factors, we divide the number by the factor. This keeps reducing the size of the number we’re factorising, while increasing the size of the factors.
Pretty simple really isn’t it! Thoughts?
Note: I’m assuming that nobody is going to call this function that is a multiple of 2!
March 20, 2008
What does the “m n 3″ or “m n d” syntax do? It’s almost like m is an operator (assuming it’s a similar layout to the “div n 2″ type expressions).
March 21, 2008
Think of “m n d” as another function called m with two parameters n (number) and d (divisor). In Haskell you can define functions within functions. Basically smaller helper functions which live in the scope of the function you’re working in. This allows you to define helper functions that aren’t available globally and that are very particular to your current tasks. The where keyword is used to define those internal functions.
So when the number is no longer even, I call m passing in the number and 3 (the starting point for odd number divisor testing). Then m recursively calls itself until the biggest divisor is found.
Simple as that mate
March 22, 2008
Ah yes. That makes much more sense now. Thanks mate!
April 20, 2008
If you do need a list of primes, it’s fairly straightforward…
integersFrom n = n : map ( 1) (integersFrom n)
primes = 2 : filter isPrime (integersFrom 3)
isPrime n =
let iterPrime (h:list) | (h*h) > n = True
| (0 == (n `rem` h)) = False
| otherwise = (iterPrime list)
in iterPrime primes
main = print $ takeWhile (<300) $ primes
April 20, 2008
In this case, no you don’t need a list of primes. It not only makes the code bigger than required, but it’s also slower.
Euler 7 (solved a while ago, yet to post) required primes to solve the problem, and I’ll be posting my primes generator when I post about that.
Besides, that implementation looks like it has been “borrowed” :P I’ve seen it before somewhere.
April 21, 2008
That particular implementation is all my own work (which is why it is so nasty-looking). The algorithm itself I believe dates back to 300BC, and has indeed been “borrowed”. But if a problem has been solved, and you know it’s been solved, is there any point concocting yet another half-baked solution?
I’d been interested to see some evidence of why it’s slower to use a stream of primes rather than a stream of odd numbers. I’d guess that it’s because dividing by 15 is the same as dividing by 3 then 5.
If you can provide execution times, then I’m not going to argue against the facts.
April 21, 2008
Aye, the implementation is, but the algo isn’t. Hence the recognition
I totally agree with your premise — reuse a well-known solution when you can. No point in labouring to do it yourself unless you have a better understanding of the problem than the person who created the well-known algo. Then of course you’re not re-inventing the wheel, you’re just improving it!
I shall get some stats for you and throw them into the post and let you know when it’s done. By the looks of it (based on your blog) you’ve done some testing yourself already