Euler : Problem 60

Posted by TAKAIY 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の倍数を省くとか、
・ 枝刈りをする
  まったく思いつかない
・ リストの更新処理の高速化
  データの持ち方をちゃんと考えないと





0 コメント:

コメントを投稿