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