Project EulerをClojureでおさらいシリーズ。

週1門以上のペースじゃないと出題に追いつけないこの企画。
今回は Problem 3。

オリジナルはこちら

日本語訳：

13195 の素因数は 5, 7, 13, 29 である。

600851475143 の素因数で最大のものを求めよ。

素因数は対象の平方根を超えることはないので 2〜sqrt(N) のあいだの素数を調査すればよいことになる。

その昔、Rubyで解いたときのがこれ。

#!/usr/bin/env ruby
def lpf(num)  num_sqrt = Math::sqrt(num)
  (2..num_sqrt).each do |x|
    while num % x == 0
      num = num / x
    end
    return x if num == 1
  end
end
 
p lpf(600851475143)

もう笑っちゃうほど手続き型です。

素数列は使わずに整数列そのままでループしています。

2 → sqrt(num)の整数xで順に：
・numが割り切れればxで割れるだけ割る→商を次のnumに。
・numが１になったらそのときのxが答え。
・先頭に戻る（次のx）。

こんどはClojureで書くために再帰を使った定義を考えてみる。

ループの初期値(n = 元の数, d = 2)として：
・n = d なら d が答え。
・割り切れたら割り切れなくなるまで割って(商, d+1)で再帰。
・Numがdで割り切れなければ (n, d+1)で再帰。

あー、なんか思考が毒されてるぞ。
あやうく div_max とかいうムダな関数を定義することろだったわ。

書き直すと

ループの初期値(n = 元の数, d = 2)として：
・n = d なら d が答え。
・割り切れたら(n/d, d)で再帰。
・Numがdで割り切れなければ (n, d+1)で再帰。

コードにしてみるとこんな感じに：

(defn largest-prime-factor
  "Returns a largest prime factor."
  [number]
  (loop [n number d 2]
    (cond (= n d) n
          (= 0 (rem n d)) (recur (/ n d) d)
          :else (recur n (inc d)))))
 
(largest-prime-factor 600851475143)

2行目の文章は関数のドキュメントです。 この部分は習慣としてきちんと書くように心がけてみる。

意外と手続き型の考え方ってのは染みついているものだと実感。
再帰は不自由なようで自由度が高いような、不思議な感じです。