MacBook Pro A1502

Euler problem 12.1.2

.

```(defun good-reverse (lst)
(labels ((rev (lst acc)
(if (null lst)
acc
(rev
(cdr lst)
(cons (car lst) acc)))))
(rev lst nil)))

(defparameter *primes* '(2 3 5))

(defun primeFactors (n)
(factor-iter n *primes* '()))

(defun range (max &key (min 0) (step 1))
(loop :for n :from min :below max :by step
collect n))

(defun primep (x)
(NULL (cdr (primeFactors x))))

(defun factor-iter (n p-list acc-list)
(let* ((p (car p-list))
(ps (cdr p-list)))
(cond ((> (* p p) n)
(good-reverse (cons n
acc-list)))
((eql (mod n p) 0)
(factor-iter (floor n p)
p-list
(cons p acc-list)))
((NULL ps)
(let* ((op
*primes*)
(num-extend
(range (1+
(ceiling (sqrt n)))
:min (+ p 2)
:step 2))
(primes-extend
(remove-if-not
#'primep
num-extend)))
(if (NULL primes-extend)
(cons n acc-list)
(progn
(setf *primes*
(append op primes-extend))
(factor-iter n
primes-extend
acc-list)))))
('t
(factor-iter n ps acc-list)))))

(defmacro prime-filter (n)
`(remove-if-not #'primep
(cons 2
(range (1+ ,n)
:min 3
:step 2))))

(time (length (prime-filter 20000000)))

;; Evaluation took:
;; 13.056 seconds of real time

;; 1270607
```

— Me@2023-03-28 11:51:24 AM

.

.