Y箱

問題3は、素数の問題。
この後にも何個か出て来たし、これからも沢山出てくるんだろうけど、これは手強い。

まずは、できなかったやつ。 10000位でメモリーオーバーフローになっちまった

;;
;; overflow with 10000
(defn prime-nums-under [n]
  (let [limt (inc (int (sqrt n)))]
    (loop [prm-nums () candidate (range 2 (inc n))]
      (let [target (first candidate)]
        (if (>= target limt)
          (concat prm-nums candidate)
          (recur (concat prm-nums (list target))
                 (filter #(not (zero? (rem % target))) 
                         (rest candidate))))))))
;;

で、作りなおしたのがこれ。

;;
;; java.lang.OutOfMemoryError: Java heap space
(loop [tester 600851475143
       target-prim (prime-nums-under (floor(sqrt tester)))
       successor 1]
  (cond (empty? target-prim) successor
        (zero? (rem tester (first target-prim))) 
           (recur tester (drop 1 target-prim) (first target-prim))
        true (recur tester (drop 1 target-prim) successor)))
;;

でもだめ。

しょうがないから、素数を作るのじゃなくて、素数かどうか1つずつ確認してみた。

;;
;; SUCCESS
(defn is-prime? [n]
  (zero? (count (filter #(= (rem n %) 0) (range 2 (inc (int (sqrt n))))))))

(loop [tester 600851475143
       target-num (floor (sqrt tester))]
  (if (and (zero? (rem tester target-num))
           (is-prime? target-num))
       target-num
       (recur tester (- target-num 1))))
;;

できた。
でもなぁ。
なんか気に入らない。 そのうち直す。