Solving Google Treasure Hunt Puzzle 4: Prime Numbers

You're viewing a comment by Bron Gondwana and its responses.

Bron Gondwana Permalink
June 07, 2008, 15:03

I did it in perl - and not terribly efficiently. Generated the primes up to 30,000,000 because that's about all that the simple sieve code I found would do in the 4Gb of memory I had available, figured it was probably enough.

And keeping ALL the lists in memory as both arrays and hashes was actually not too bad - wrote it in about 10 minutes and it took another 5 to run. Woot.

My first-pass recursive attempt at the robots thing was totally intractable, and the second time when I forgot to "use bigint" I actually submitted the wrong number through doing insufficient checking (oh the embarassment) - but once you figure that: value(N, M) == value(N - 1, M) + value (N, M - 1) and value (1, x) == value (y, 1) == 1, then it's pretty trivial to just build an N x M array and calculate the values.

It is nice having a multi-core modern machine with 4Gb of ram for the prime problem though - it makes brute force much cheaper, and coming up with a good algorithm for a once-off computation rather worthless.

Reply to this comment

Reply To This Comment

(why do I need your e-mail?)

(Your twitter name, if you have one. (I'm @pkrumins, btw.))

Comment Help

Type the first letter of your name: (just to make sure you're a human)

Please preview the comment before submitting to make sure it's OK.