Any tip you could give on what kind of optimization we should be looking at?
I tried a naive memoization and, of course, the timeout is still there.

I gave up some days ago on some haskell codegolf-like challenge (Weak Primality Test) and I don't want to make throwing in the towel a habit :D