Euler : Problem 58

Posted by YpsilonTAKAI On 2011年7月3日日曜日 0 コメント
数字をぐるぐる四角に並べたときに、中心から角に向う線上にある数が素数である確率が10%を下まわるのは何周並べたときかという問題。

n周めの角にくる数字は、nで表わせるので素数かどうか判定する。あと、n週での対象となる数の数もnで表わせるので計算して、割合を出す。



;;
;; Problem 58 : 2011/6/21
"Elapsed time: 3646.419866 msecs"

(defn corner-set [n]
(let [side-len (- (* n 2) 1)
bottom-right (expt side-len 2)
bottom-left (- bottom-right (- side-len 1))
top-left (- bottom-right (* 2 (- side-len 1)))
top-right (- bottom-right (* 3 (- side-len 1)))]
[top-right top-left bottom-left bottom-right]))



(loop [n 2
prime-count 0]
(let [new-prime-count (+ prime-count
(count (filter is-prime? (butlast (corner-set n)))))
corner-count (- (* n 4) 3)
prime-ratio (/ new-prime-count corner-count)]
(if (< prime-ratio 1/10)
[n (- (* n 2) 1)]
(recur (inc n) new-prime-count))))
;;

0 コメント:

コメントを投稿