のてすきあ − 完全独習非プログラマー −

Haskell で Project Euler を解く素人遊び

Problem 60

3,7,109,673 の素数の組は、それぞれをつなぎ合わせた数(例:7109, 1097, 673109など)も全て素数になる。そのように連結可能な5つの数の組を探し、その中で5数の和が最も小さくなるものを見つける。

 ある条件を満たす素数を見つけるパターンは、計算に時間がかかりがちだが、その中でもなるべく効率的な方法を見つけたい。ナイーブに全検索すると絶対に計算が終わらないので、いかに実装するかである。
 実装のイメージはネットワークである。3,7,11...と素数を順番に空間に配置していき、その度に既に配置されていた数と連結可能なら線を繋いでいく。(実装上は線で繋がっているものをリストにした)
 3から始まって、[3],[7],[7,3],[11],[11,3],[13],[17],[17,3],[19],[19,7],[19,13],[23],[23,11],[29],[31],[31,3],[31,19],[37],[37,3],[41],[43],[47],[47,23],[53],[59],[59,3],[61],[61,7],[61,13],[67],[67,3],[67,37],[67,37,3], ... と順々に点を打っていくイメージである。(伝わるか?)

 自分の近くに連結可能な仲間がいなくても、ずっと遠くにいる可能性があるため、排除できる数がない。例えば41は近くに友達は見つからないが、ずっと先の227とペアになることができる。また、3つ組があったとしても、そのうち2つと仲間になれる別の数が見つかる可能性もある。そういう可能性を余さず評価していくための関数がfindGroupである。

 mainをdo式にしたのは、単純に数の組とその和の両方を出力するのに、do式の方が書きやすかったからというだけで、あまり意味はない。

 頑張ったつもりだが、それでもコンパイルして結果が返ってくるまで3分かかる。

 

速い方法があるかも知れない★