With some of the problems, I'm starting to run up against the one-minute execution time guideline.
From a computational perspective, I feel as if I'm still reasonably well equipped to handle the problems. Various parts of my Coursera and Udacity education have come in handy, including dynamic programming, basic cryptography, and the general approach to breaking down problems as presented in Peter Norvig's class.
From a number theoretical perspective, though, I'm running into some trouble. In Problem 60, for example, the naive brute-force approach runs in O(n^5), where n is on the order of 10,000 (and possibly much larger). There are surely ways to cut down the search space, but I need to do some more reading on primes.
On the subject of primes, I need to find a better primality test. So far I've been able to get by with a combined approach of:
- generating all primes that are less than 10,000,000 via the Sieve of Erastothenes
- checking primality of larger numbers by prime factoring and counting the number of factors
Maybe the next step is to implement a faster sieve or something like the Miller-Rabin test.
