# Way

There is always a WAY.

.

```(defun sum-of-squares(x y &key (a 1) (b 1))
(+ (* a x x) (* b y y)))

(deftype candidate()
'(simple-array boolean (*)))

(defmacro get-sieve-function(a b mod-results)
`(lambda(x y)
(let* ((n (sum-of-squares x y :a ,a :b ,b))
(r (mod n 12)))
(when (and (<= n limit)
(not (null
(member r ,mod-results))))
(setf (aref candidates n)
(not (aref candidates n)))))))

(defun get-atkin-prime-candidates-map(limit)
(let* ((lmt (isqrt limit))
(candidates (make-array
(1+ limit)
:initial-element nil))
(stage1 (get-sieve-function 4 1 '(1 5)))
(stage2 (get-sieve-function 3 1 '(7)))
(stage3 (get-sieve-function 3 -1 '(11))))
(declare (type candidate candidates))
(declare (optimize (speed 3)))
(loop for x from 1 to lmt do
(loop for y from 1 to lmt do
(progn
(funcall stage1 x y)
(funcall stage2 x y)
(when (> x y)
(funcall stage3 x y)))))
candidates))

(defun atkin-sieve-map(candidates)
(let ((len (length candidates)))
(loop for i from 1 to (1- len)
when (aref candidates i)
do (loop for j from 1
for n = (* j i i)
while (< n len)
do (setf (aref candidates n) nil))))
(setf (aref candidates 2) T)
(setf (aref candidates 3) T)
candidates)

(defun eratosthene-sieve-map(limit)
(let ((candidates
(make-array
(1+ limit) :initial-element T)))
(declare (type candidate candidates))
(declare (optimize (speed 3)))
(progn
(setf (aref candidates 0) nil)
(setf (aref candidates 1) nil))
(loop for i from 2 to limit
when (aref candidates i)
do (loop for j from (+ i i) to limit by i
when (aref candidates j)
do (setf (aref candidates j) nil)))
candidates))

;; This is free software released
;; into the public domain.
;;
;; ykm

(defun get-primes(limit
&key
(generator :eratosthene))
(let ((candidates
(case generator
(:atkin (atkin-sieve-map
(get-atkin-prime-candidates-map
limit)))
(:eratosthene (eratosthene-sieve-map
limit))
(otherwise
(error "not valid type
(:atkin :eratosthene)")))))
(declare (type candidate candidates))
(loop for i from 0 to (1- (length candidates))
when (aref candidates i)
collect i)))

(format t "soe: ~d
" (time (length (get-primes 12345678))))

(format t "soa: ~d
" (time (length (get-primes 12345678
:generator :atkin))))

(defmacro log10 (x)
`(/ (log ,x) (log 10)))
```

.

— Me@2022.09.06 03:24:36 PM

.

.