Clojure入門 - Project Eulerを解いてみる 問27
x=0..nで、 x2 + a*x + b がすべて素数となるnの値が最大となるaとbを求める。
エラトステネスの篩の出番か!とも思ったが、JavaのisProbablePrimeを使ってみる。
(def certainty 5) (defn prime-nm? [n] (.isProbablePrime (BigInteger/valueOf n) certainty)) (def prime? (memoize prime-nm?))
メモ化は大事。
(defn quad [a b x] (+ (* x x) (* a x) b)) (defn quad-prime-len-nm [[a b]] (->> (range) (map #(quad a b %)) (take-while prime?) (count))) (def quad-prime-len (memoize quad-prime-len-nm))
メモ化は大事。(二回目
実は大事である理由は違う。prime?は同じ数字を何回も評価する可能性があるのでmemoizeしているが、quad-prime-lenはmax-keyを使うのでmemoizeが必要になる。map (juxt quad-prime-len identity)のパターンでいくならmemoizeの必要はない。
(apply * (apply max-key quad-prime-len (for [a (range -999 1000) b (filter prime? (range 2 1000))] [a b])))
aとbの上限・下限についてももうちょっと詰められるが、上記のコードで2秒強で走るので置いておく。