Skip to content

Instantly share code, notes, and snippets.

What would you like to do?
racket prime factorization
(define (eratosthenes n)
(define (sift list p)
(filter (lambda (n)
(not (zero? (modulo n p))))
(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