(defun sieve-of-atkin (lim) (let* ((slim (sqrt lim)) (p (make-array (+ lim 60) :initial-element 0))) (loop for v from 1 to (floor slim 2) do (let ((x (1+ (* 4 v v))) (y 8)) (loop while (<= x lim) do (when (not (= (mod x 12) 9)) (setf (aref p x) (logxor (aref p x) 1))) (setf x (+ x y) y (+ y 8))))) (loop for v from 1 to (floor (/ slim (sqrt 3))) by 2 do (let ((x (+ (* 3 v v) 4)) (y 12)) (loop while (<= x lim) do (when (= (mod x 12) 7) (setf (aref p x) (logxor (aref p x) 1))) (setf x (+ x y) y (+ y 8))))) (loop for v from 2 to (floor (/ slim (sqrt 2))) do (let ((x (1- (* 2 v (1+ v)))) (y (- (* 4 v) 8))) (loop while (and (<= x lim) (<= 0 y)) do (when (= (mod x 12) 11) (setf (aref p x) (logxor (aref p x) 1))) (setf x (+ x y) y (- y 8))))) (loop for n from 5 to (floor slim) do (when (/= (aref p n) 0) (loop for z from (* n n) below lim by (* n n) do (setf (aref p z) 0)))) (setf (aref p 2) 1 (aref p 3) 1) p)) (defun main (&rest argv) (declare (ignorable argv)) (let* ((q (read)) (p (sieve-of-atkin 5000001))) (dotimes (_ q) (let* ((a (read)) (s (read))) (format t "~d~%" (if (= (aref p s) 1) (if (zerop (mod a s)) 0 1) -1)))))) (main)