Euler : Problem 3

Posted by TAKAIY On 2011年4月9日土曜日 0 コメント
問題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))))
;;


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


0 コメント:

コメントを投稿