Actually, there is a solution that takes 0.52 seconds: http://www.spoj.pl/ranks/PRIME1/lang=LISP%20sbcl