Clojure入門 - Project Eulerを解いてみる 問3
大きい数字を素因数分解する話である。
とりあえずまずはヘルパー関数。名前を付けておくとやはり読みやすいように思う。
(defn is-factor [f n] (zero? (mod n f))) (defn lte-root [n m] (<= (* n n) m))
個人的にはlte-root
が微妙。ただless-than-or-equal-to-root
だと非常に冗長だし難しいところ。思い切って<=root
でもいいのか?
次は素数p_n以下のすべての素数のvectorを受け取り、次の素数p_(n+1)を末尾に加えた新vectorを返す関数。
(defn next-prime-vec [prime-vec] (letfn [(is-prime [n prime-vec] (every? #(not (is-factor % n)) (take-while #(lte-root % n) prime-vec)))] (loop [n (inc (last prime-vec))] (if (is-prime n prime-vec) (conj prime-vec n) (recur (inc n))))))
is-prime
関数は汎用性が非常に低い(素数のリストを入力として受け取る必要がある)のでローカル関数化。読みやすいかどうかはまだ微妙なので、現段階ではかなり手探り。
最後に素因数分解の計算。
(defn prime-factors [n] (loop [num n factors [] primes [2]] (let [p (last primes)] (cond (= 1 num) factors (not (lte-root p num)) (conj factors num) :else (if (is-factor p num) (recur (/ num p) (conj factors p) primes) (recur num factors (next-prime-vec primes)))))))
ここまでくるとロジックは比較的明快・宣言的に記述できる。
小さい順で素数を調べていって、n
を余りなく割れるなら素因数のvectorに追加、
n`を割って再帰。割れないなら次の素数で再帰。
終了条件はn = 1
かn < p*p
で後者の場合はn
そのものが素因数。
問題文への回答としては
(println (last (prime-factors 600851475143)))
で出る。素因数が大きさの順で並んでいることを活用。