I have been doing some of the exercises at Project Euler lately. Project Euler describes themselves as:
A series of challenging mathematical/computer programming problems that will require more than just mathematical insights to solve. Although mathematics will help you arrive at elegant and efficient methods, the use of a computer and programming skills will be required to solve most problems.
It has been a lot of fun to code these up in my language du jour, Python. There are a couple of problems that Python’s built in libraries have made trivial. I have to admit the most enjoyable part for me is having problems that require efficiency in algorithm. For the simpler problems, I usually just quickly hack together the “naive” brute force method, figure out that it doesn’t scale and then start investigating how I can fix it. Doing this, you will exercise your mathematics, computer science and programming skills, something that a lot of programming doesn’t do. I convinced my girlfriend to work with me on one of the exercises, and of course she picked one of the Prime Factorization problems. The naive brute force algorithm would not be an option for the large composite number given, so we ended up hacking together a Sieve of Eratosthenes. Ultimately, we got a version working, but it was still pretty inefficient, only returning the answer in about an hour. An optimal version should be able to do it within seconds. Obviously there is some “refactoring” to do.