どの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の倍数を省くとか、
・ 枝刈りをする
まったく思いつかない
・ リストの更新処理の高速化
データの持ち方をちゃんと考えないと
解くのにすごく手間どった。なにしろ計算が終らない。ロジックに問題があるのだとばかり思っていたら、そうではなくて、素数判定の考慮漏れだったという情無い落ち。
といっても、解くのに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 コメント:
コメントを投稿