Problem 3, and fix up utils.
author |
Steve Losh <steve@stevelosh.com> |
date |
Sat, 09 Apr 2016 17:16:13 +0000 |
parents |
(none) |
children |
3512c67e0138 |
(in-package #:euler)
(defun prime-factorization (n)
"Return the prime factors of `n`."
;; from http://www.geeksforgeeks.org/print-all-prime-factors-of-a-given-number/
(let ((result (list)))
(while (evenp n) ; handle 2, the only even prime factor
(push 2 result)
(setf n (/ n 2)))
(loop :for i :from 3 :to (sqrt n) :by 2 ; handle odd (prime) divisors
:do (while (dividesp n i)
(push i result)
(setf n (/ n i))))
(when (> n 2) ; final check in case we ended up with a prime
(push n result))
(nreverse result)))