Euler : Problem 50

Posted by TAKAIY On 2011年6月29日水曜日 0 コメント
100万以下の素数で、もっとも大くの連続する素数の和で表わされるものを求める問題。

そのまま解いた。
素数のリストについて、初めから順に足していって、結果が素数になるかどうか都度判定する。
素数でなくなったら、素数のリストの先頭をとりのぞいてまた同様のことをする。
素数でなくなったときの情報を、前の結果と比べて結果を更新する。

時間かかりすぎ。



;;
;; Problem 50 : 2011/6/14
;; "Elapsed time: 276190.732342 msecs"

(defn longest-seq [coll max-val]
(loop [forward-coll []
rest-coll coll
max-seq []]
(if (empty? rest-coll)
max-seq
(let [next-foward (conj forward-coll (first rest-coll))
sum-of-coll (reduce + next-foward)]
(cond (> sum-of-coll max-val) max-seq
(is-prime? sum-of-coll)
(recur next-foward (rest rest-coll) next-foward)
:else
(recur next-foward (rest rest-coll) max-seq ))))))


(loop [primes (prime-nums-under 1000000)
max-count 0
res-seq []]
(if (< (count primes) max-count)
res-seq
(let [new-long-coll (longest-seq primes 1000000)
new-count (count new-long-coll)]
(if (< new-count max-count)
(recur (rest primes) max-count res-seq)
(recur (rest primes) new-count new-long-coll)))))
;;

0 コメント:

コメントを投稿