Euler : Problem 60

Posted by YpsilonTAKAI On 2011年11月14日月曜日 0 コメント
どの2つを取ってつないでも素数になる5つの素数の組をさがす問題

解くのにすごく手間どった。なにしろ計算が終らない。ロジックに問題があるのだとばかり思っていたら、そうではなくて、素数判定の考慮漏れだったという情無い落ち。

といっても、解くのに15分以上かかってしまっているので、情無いのには変りない。

全数アタック以外の方法を思いつかないし、出た答えを見ても、うまい枝刈りの方法も思いつかないので、現状ではこれがほぼベスト。8けた以上の数の素数判定が早くなれば、かなり減りそうだけれど、1分にはほど遠い感じ。





方法はこんな感じ。

素数の列を作る。2と5は題意から除外する。

3 7 9 11 13 17 ......

1こずつ取ってきて、組をつくる。
そのときこういうことをする。
a 自分だけの組
b もともとあった組
c もともとあった組すべてに自分を加えた組
できたものを、要素の数の多い順に並べる。

初めは(3)。 これに7を追加するには
a (7)
b (3)
c (3 7)
なので、できるのは、
(3 7) (3) (7)

9を追加すると

a (9)
b (3 7) (3) (7)
c (3 7 9) (3 9) (7 9)
よって、
(3 7 9) (3 7) (3 9) (7 9) (3) (7) (9)

また、追加するとき、その組が題意に沿っているかどうかの確認もする。
たとえば、(3 7 9)は、39が素数でないので除外する。

こうしていくと、ある素数以下の素数でつくられた、題意に沿ったすべての素数の組をつくることができる。 最初に5個になったものが答。

この方式で高速化するなら、下記のやうなことをしてみるかな。
・ 素数判定の高速化
  3の倍数を省くとか、
・ 枝刈りをする
  まったく思いつかない
・ リストの更新処理の高速化
  データの持ち方をちゃんと考えないと


(use 'clojure.contrib.math)
(defn concat-num [n m]
(let [zeros (first (drop-while #(<= % m) (iterate #(* 10 %) 1)))]
(+ (* n zeros) m)))
(defn prime-pair? [n m]
(and (is-prime? (concat-num n m))
(is-prime? (concat-num m n))))
(defn all-make-prime-pair? [p-set p]
(every? true? (map #(prime-pair? p %) p-set)))
(defn insert-pset [primeset-list pset]
(loop [h-list []
t-list primeset-list]
(cond (empty? t-list) (conj h-list pset)
(> (count pset)(count (first t-list))) (concat h-list [pset] t-list)
:else (recur (conj h-list (first t-list))
(next t-list)))))
(defn create-next [primeset-list pnum]
(filter #(all-make-prime-pair? (butlast %) (last %))
(map #(conj % pnum)
(conj primeset-list []))))
(defn pe60 [seq-count]
(loop [primeset-list []
primes (cons 3 (drop 3 (get-prime-list)))] ;; remove 2 and 5
(if (>= (count (first primeset-list)) seq-count)
(first primeset-list)
(let [nextset (create-next primeset-list (first primes))]
(recur (reduce insert-pset primeset-list nextset)
(next primes))))))
;; "Elapsed time: 965709.946376 msecs"
;; ouch!
view raw pe_60.clj hosted with ❤ by GitHub



ラベル: ,

0 コメント:

コメントを投稿