SketchyLISP Stuff | Copyright (C) 2006 Nils M Holm |
[ More Sketchy LISP Stuff ] |
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))
[ More Sketchy LISP Stuff ] |