factors

Language: R5RS Scheme

Purpose: Compute the prime factors of an integer.

Arguments:
N - number

Implementation:

(define (factors n)
  (letrec
    ((rest+exponent
       (lambda (n m)
         (letrec
           ((div
              (lambda (n m r)
                (cond ((zero? (modulo n m))
                    (div (quotient n m) m (+ 1 r)))
                  (else (cons n r))))))
           (div n m 0))))
     (add-expt
       (lambda (b e r)
         (cond ((zero? e) r)
           ((= e 1) (cons b r))
           (else (cons (list 'expt b e) r)))))
     (factorize
       (lambda (n d r)
         (let ((lim (sqrt n)))
           (letrec
             ((_factorize
                (lambda (n d r)
                  (let ((rest/exp (rest+exponent n d)))
                    (let ((m (car rest/exp))
                          (e (cdr rest/exp)))
                      (cond ((< m 2) (add-expt d e r))
                        ((> d lim) (add-expt n 1 r))
                        (else (_factorize m
                                (if (= d 2) 3 (+ d 2))
                                (add-expt d e r)))))))))
             (_factorize n d r))))))
    (cond ((< n 1)
        (bottom (list 'factors n)))
      ((= n 1) 1)
      (else (let ((facts (factorize n 2 '())))
              (cond ((null? (cdr facts))
                  (car facts))
                (else (cons '* facts))))))))

Example:

(factors 24) 
=> (* 3 (expt 2 3))