Euler : Problem 5

Posted by TAKAIY On 2011年4月9日土曜日 0 コメント
また出てきた素数。
素因数分解して解の員数を出して解いているんだけど、素数列をその度に作っているので非効率。
今後のためにも、素数列は取っておけるようにしようかなぁ。

;;
;; Problem 5 : 2011/4/7
;; prime-nums-under : defined above

(defn factors [n]
;; (foctors 12) => (2 2 3)
(loop [factor-list ()
target n
prime-list (prime-nums-under target)]
(if (or (= target 1) (empty? prime-list))
(reverse factor-list)
(let [one-prime (first prime-list)]
(if (zero? (rem target one-prime))
(recur (cons one-prime factor-list) (/ target one-prime) prime-list)
(recur factor-list target (rest prime-list)))))))


(defn fusion
;; (fusion '(2 3 3) '(3 4 4)) => (2 3 3 4 4)
([list1 list2]
(fusion list1 list2 ()))
([list1 list2 res-list]
(cond
(empty? list1) (sort (concat res-list list2))
(empty? list2) (sort (concat res-list list1))
true
(let [top-of-1 (first list1)
top-of-2 (first list2)]
(cond
(= top-of-1 top-of-2)
(recur (rest list1) (rest list2) (cons top-of-1 res-list))
(< top-of-1 top-of-2)
(recur (rest list1) list2 (cons top-of-1 res-list))
(> top-of-1 top-of-2)
(recur list1 (rest list2) (cons top-of-2 res-list)))))))

(reduce * (reduce fusion (map #(factors %) (range 2 21))))

;;

0 コメント:

コメントを投稿