Jul 2009
1 / 3
Jul 2009
Sep 2020
maweaver
Jul '09

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?

  • created

    Jul '09

  • last reply

    Sep '20
  • 2

    replies

  • 873

    views

  • 2

    users

maweaver
Jul '09

After a lot of hair-pulling, I finally got it to work. I littered my code with type declarations

(declare (type (unsigned-byte 64) n) (optimize (safety 0) (speed 3)))

With a few other optimizations, this got it down to 5.5s, just under the time limit.

11 years later
madhusurisetti
Sep '20

this code works well
0.6seconds for 1000000000 1000100000

(defun divp (a b)
“tell if a is divisible by b”
(if (= (mod a b) 0) t))

(defun parse-ints (s)
“return a list of integers from a string”
(with-input-from-string (in s)
(loop for x = (read in nil nil) while x collect x)))

(defun lgen (lower upper &optional qualifier)
“generate a list that whose elements satisfy qualifier”
(when (null qualifier)
(setf qualifier #’(lambda (x) t))) ; A function that returns true for any argument
(do ((x lower (1+ x))
(lst nil))
((> x upper)
(nreverse lst)) ; The combination of push & nreverse is the standard lisp idiom for accumulating a list
(when (funcall qualifier x)
(setf lst
(push x lst)))))

(defun primep (n)
(cond ((member n ‘(2 3 5 7 11 13 17 19)) (return-from primep t)) ; fix this later!!!
((or (evenp n) (= n 1)) (return-from primep nil))
((numberp n) (progn
(mapcar #’(lambda (x)
(when (divp n x)
(return-from primep nil)))
(lgen 3 (isqrt n) #'oddp))
t))))

;; ===================================================================================================================================
;; Code Starts Here!!!
;; ===================================================================================================================================

(defparameter upper-limit 1000000000)

(defparameter prime-list (lgen 0 (isqrt (+ 5000 upper-limit)) #'primep))

(defun newprimep (n)
“optimized primep”
(when (< n 30) (if (primep n) (return-from newprimep t) (return-from newprimep nil)))
(let ((sqrt-of-n (isqrt n)))
(loop for x in prime-list until (> x sqrt-of-n) do
(if (divp n x) (return-from newprimep nil))))
t)

(defun gen-primes-between (lower upper) ; inclusive
(lgen lower upper #'newprimep))

(defun spoj ()
(let ((n (car (parse-ints (read-line)))) (lst nil))
(loop
for x from 1 to n do
(push (parse-ints (read-line)) lst))
(dolist (x (nreverse lst))
(format t “~%~{~a~%~}” (gen-primes-between (first x) (second x))))))

(spoj)