(Nils' Scheme Snippets)

Paren matching: OFF | Category: math | Overview | Scheme Books | License

(factor integer) => list

Purpose

Factor an integer down to its constituent primes. The resulting list has the form ((base exponent) ...)

Arguments

n	integer to factor

Example

(factor 24) => ((3 1) (2 3))

(define (factor n)
  (letrec
    ((rest+exponent
       (lambda (n m)
         (letrec
           ((div
              (lambda (n m r)
                (if (zero? (modulo n m))
                    (div (quotient n m) m (+ 1 r))
                    (cons n r)))))
           (div n m 0))))
     (add-expt
       (lambda (b e r)
         (cond ((zero? e) r)
               (else (cons (list b e) r)))))
     (factorize
       (lambda (n d r)
         (let ((lim (sqrt n)))
           (letrec
             ((factorize3
                (lambda (n d r)
                  (let* ((rest/exp (rest+exponent n d))
                         (m (car rest/exp))
                         (e (cdr rest/exp)))
                    (cond
                      ((< m 2) (add-expt d e r))
                      ((> d lim) (add-expt n 1 r))
                      (else (factorize3 m
                                        (if (= d 2) 3 (+ d 2))
                                        (add-expt d e r))))))))
             (factorize3 n d r))))))
    (cond
      ((< n 1) (wrong "factors: operand not positive" n))
      ((= n 1) 1)
      (else (factorize n 2 '())))))