Skip to content

Instantly share code, notes, and snippets.

@dstnbrkr
Created March 4, 2011 21:02
Show Gist options
  • Star 1 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save dstnbrkr/855700 to your computer and use it in GitHub Desktop.
Save dstnbrkr/855700 to your computer and use it in GitHub Desktop.
racket prime factorization
(define (eratosthenes n)
(define (sift list p)
(filter (lambda (n)
(not (zero? (modulo n p))))
list))
(define (iter nums primes)
(let ((p (car nums)))
(if (> (* p p) n)
(append (reverse primes) nums)
(iter (sift (cdr nums) p) (cons p primes)))))
(iter (cdr (build-list n add1)) '()))
(define (divides? p q)
(zero? (modulo q p)))
(define (prime-factors n)
(let loop ((primes (eratosthenes n)))
(cond ((memq n primes) (list n))
((divides? (car primes) n)
(cons (car primes) (prime-factors (/ n (car primes)))))
(else (loop (cdr primes))))))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment