読者です 読者をやめる 読者になる 読者になる

Arantium Maestum

プログラミング、囲碁、読書の話題

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 = 1n < p*pで後者の場合はnそのものが素因数。

問題文への回答としては

(println (last (prime-factors 600851475143)))

で出る。素因数が大きさの順で並んでいることを活用。