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

Haskell で Project Euler を解く素人遊び

Problem 51

2桁の数 *3 の*に数字を入れると、13,23,43,53,73,83 の6つの素数を得る。同様に5桁の数 56**3 の*に同じ数字を入れたもののうち、56003, 56113, 56333, 56443, 56663, 56773, 56993 の7つが素数となる。同じルールで数のうちのいくつかの数字を同じ数字に置き換えた時に、8つの素数が得られる最小の数(先の例だと13や56003)を求める。*は必ずしも隣り合っている必要はない。

 50問の壁の向こうはいきなりハードルが高い。これはここまでで最も難しいというか、苦労した問題であった。一番の難点は数字をいくつ置き換えても良いところにある。数字の置換をどのようにコーディングするかという問題もあるし、単純に(機械的に)調べるだけなら、軽く数億を超えるケースを調査しなければならないという効率の問題もある。


 まず、置換については、さんざん悩んだ末に文字列として処理することにした。その際に数字→数字と置換するよりも、遠回りのようだがいったん置換する場所にポインタ(自分のコードでは文字 '*' にした)をおいて、ポインタを数字に置き換えていく方法を取った。間に余計な操作を1つ挟むので効率が低下する可能性があるが、そのように段階を踏んで操作しないと頭がついていかないので、諦めてそのようにした。  その際に末尾は置換不要(10の間隔の中に素数が8つもあることはあり得ない)とか、先頭にゼロを置かないとか、そういう当たり前に排除できるものは排除した。

 あとは総当りで調べるのみである。問題文から下限を56003とおけるので、その先のみを探索した。

 

さすがオーバー50☆