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