Clojure入門 - Project Eulerを解いてみる 問２７

第二十七問

x=0..nで、 x² + 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の上限・下限についてももうちょっと詰められるが、上記のコードで２秒強で走るので置いておく。