Has anyone gotten this to work without getting a Time Limit Exceeded error? Ok, that's a rhetorical question, according to the top page 6 people of 6830 have, which isn't exactly encouraging. I've been working on it all day and it's driving me nuts.
My current method is to generate a list of all primes from 1 to 50 on startup using the naive gcd method (the time to do this is negligible). Then, for possible prime, I do a check against 1, then check the modulus with each of the precomputed primes.
If that passes, I do the probabilistic Miller-Rabin test as described on wikipedia for values a = 2 3 5 7 11 13. I am doing modular exponentiation for the mod(x^2, d) step, rather than calculating it directly.
I've tried playing around with many different variations on this, including calculating a different number of primes at startup (or just checking mod 2), doing the deterministic version of the Rabin-Miller test, tossing in a Little Fermat test up front to weed out some composites, etc. My current method is the fastest, but it still takes ~1.5-3.5 seconds for me to do 10 x 1000000000 1000100000, which isn't really that great.
It's probably also worth mentioning that I'm diffing against a list of values generated using the naive method, so I'm pretty sure my algorithm is correct.
I'm new to common lisp, I'm wondering if there's something about the language that's tripping me up? In particular, I'm wondering if the values are being automatically promoted from integers to an arbitrary-precision format that is operating slowly. I think the values in this problem should fit into a 64-bit integer, but I'm not sure how to force it to use that. I'm also using the LOOP construct extensively, are there any known performance problems with this vs do, etc?