; gcd by factoring

(define (factors n)
  (let ((wheel '#(1 2 2 4 2 4 2 4 6 2 6)))
    (let loop ((n n) (f 2) (fs (list)) (w 0))
      (if (< n (* f f)) (reverse (cons n fs))
        (if (zero? (modulo n f))
            (loop (/ n f) f (cons f fs) w)
            (loop n (+ f (vector-ref wheel w)) fs
                  (if (= w 10) 3 (+ w 1))))))))

(define (common lt? xs ys)
  (let loop ((xs xs) (ys ys) (zs (list)))
    (cond ((or (null? xs) (null? ys)) (reverse zs))
          ((lt? (car xs) (car ys)) (loop (cdr xs) ys zs))
          ((lt? (car ys) (car xs)) (loop xs (cdr ys) zs))
          (else (loop (cdr xs) (cdr ys) (cons (car xs) zs))))))

(define (gcd-by-factoring m n)
  (apply * (common < (factors m) (factors n))))

(display (gcd-by-factoring 24 60)) (newline)
(display (gcd-by-factoring 11111111 13290059)) (newline)