; the prime ant

(define (lpf n) ; least prime factor
  (let ((wheel '#(1 2 2 4 2 4 2 4 6 2 6)))
    (let loop ((f 2) (w 0))
      (if (< n (* f f)) n
        (if (zero? (modulo n f)) f
          (loop (+ f (vector-ref wheel w))
                (if (= w 10) 3 (+ w 1))))))))

(define (prime? n) (= (lpf n) n))

(define (prime-ant n . verbose?)
  (let ((a (make-vector (+ n 2))))
    (do ((i 0 (+ i 1))) ((= (+ n 2) i))
      (vector-set! a i (+ i 2)))
    (let loop ((n n) (p 0))
      (when (and (pair? verbose?) (equal? (car verbose?) #t))
        (display a) (display " ") (display p) (newline))
      (if (zero? n) p
        (if (prime? (vector-ref a p))
            (loop (- n 1) (+ p 1))
            (let ((q (lpf (vector-ref a p))))
              (vector-set! a p (/ (vector-ref a p) q))
              (vector-set! a (- p 1) (+ (vector-ref a (- p 1)) q))
              (loop (- n 1) (- p 1))))))))

(display (prime-ant 47)) (newline)
(display (prime-ant 20 #t)) (newline)