t3x.org / sketchy / prog / factors.html
SketchyLISP Stuff Copyright (C) 2006 Nils M Holm

factors

Conformance: R5RS

Purpose: Compute the prime factors of an integer n.

Arguments:
N - number

Implementation:

(define (factors n)
  (letrec

    ((div-m (lambda (n m r)
      (cond ((zero? (modulo n m))
          (div-m (quotient n m) m (+ 1 r)))
        (#t (cons n r)))))

    (add-expt (lambda (b e r)
      (cond ((zero? e) r)
        ((= e 1) (cons b r))
        (#t (cons (list 'expt b e) r)))))

    (factorize (lambda (n d r)
      (letrec
        ((lim (sqrt n))
        (_factorize (lambda (n d r)
          (let ((rest/exp (div-m n d 0)))
            (let ((m (car rest/exp))
                  (e (cdr rest/exp)))
              (cond ((< m 2) (add-expt d e r))
                ((> d lim) (add-expt n 1 r))
                (#t (_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)
      (#t (let ((facts (factorize n 2 '())))
            (cond ((null? (cdr facts))
                (car facts))
              (#t (cons '* facts))))))))

Example:

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