euler 3
As some of you may know I have been attempting to learn Clojure. To that end, I thought it might be a good idea to learn by solving the Euler Problems.
After tackling the first one in shell with almost zero trouble, and then finding info on how I wanted to solve the second one with little fuss, I was pleasantly surprised to find that the 3rd problem was a little more difficult.
I am not a math guru. I avoided math in school like it was giving away beatings.
As someone in the technology field it really hasn’t impacted me as much as parents would like you to believe, but it does make this challenging.
The goal was to find the largest prime factor of a rather large number (600851475143).
If you are anything like me, your first instinct is to mow this over with sheer will power. And so you will attempt to find all the factors of N, and then filter them.
However with a number this large, your first instinct will be wrong.
This C++ took around 65 minutes (on a 2Ghz Core 2 Duo) to run (and that’s just getting all the factors):
(I did it in C, so it would be as fast as I was capable of coding)
Then I read a boatload of math web sites and asked a lot of questions of folks on irc, till I got it in my head that by finding the smallest factor of a number, you could limit the data set to something more manageable.
So this morning I finally sat down and wrote out working clojure code
I am pretty happy with this, though I have already had people point out some optimizations I can make. But overall, I think as far as understanding the problem, and coming up with a reasonable solution in a functional way, I am pleased.
Then, as has been my MO lately, I started thinking about the problem in shell. And I really wanted to write code that would fit in a tweet, but I kind of got tired of thinking about it, and decided this is good enough.
So that’s that. I will probably read about optimizations for the code, but that was my best effort.
Happy Hacking!