リスト修行 素因数分解

エラトステネスのふるいで素数リストが求まったので、素数リストを元に素因数分解をしよう。

素因数分解

結構簡単

(define (factor n)
  (define p (primers n))
  (define (iter m l)
    (cond ((null? l) (= m 1) '())
          ((zero? (modulo m (car l)))
           (cons (car l)
                 (iter (/ m (car l)) l)))
          (else
            (iter m (cdr l)))))
  (iter n p))

するっと、

(factor 50) ; (2 5 5)
(factor 360) ; (2 2 2 3 3 5)
(factor 1024) ; (2 2 2 2 2 2 2 2 2 2)

おぉ。素因数分解出来ました。

思ったこと

ふるいにかけながら、素因数分解した方が早い。1024の場合激しく無駄が多い。

次の課題は

素因数分解できたので、次は組み合わせを求めなければならない。

約数までの道のりはすげぇ遠いらしいぞ。課題をミスったかもぉ〜

追記

バグがあったので修正。