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
      (funcall stage1 x y)
      (funcall stage2 x y)
      (when (> x y)
        (funcall stage3 x y)))))

(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)

(defun eratosthene-sieve-map(limit)
  (let ((candidates
       (1+ limit) :initial-element T)))
    (declare (type candidate candidates))
    (declare (optimize (speed 3)))
      (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)))

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

(defun get-primes(limit
            (generator :eratosthene))
  (let ((candidates
      (case generator
        (:atkin (atkin-sieve-map
        (:eratosthene (eratosthene-sieve-map
         (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



2022.09.06 Tuesday (c) All rights reserved by ACHK