Problem 58 (Project Euler) [原文]
1から初めて, 以下のように反時計回りに数字を並べていくと, 辺の長さが7の渦巻きが形成される.
(中略)
面白いことに, 奇平方数が右下の対角線上に出現する. もっと面白いことには, 対角線上の13個の数字のうち, 8個が素数である. ここで割合は8/13 ≒ 62%である.
渦巻きに新しい層を付け加えよう. すると辺の長さが9の渦巻きが出来る. 以下, この操作を繰り返していく. 対角線上の素数の割合が10%未満に落ちる最初の辺の長さを求めよ.
Problem 28で扱った螺旋数列の問題で、手間が省けて簡単かと思いきや、さすがにこのレベルの問題はひとひねりがあります。
「エラストテネスの篩」はせいぜい400万ぐらいまでを用意すればよかろうと思ったら、篩で用意した素数の範囲を超えても、なかなか10%を割りません。
5千万ぐらいまで確保しようとしたところで、当然のことながら、必要なメモリ領域を確保できなくなりました。
やむなく「ミラー・ラビン」でググると、親切にもWikipediaに素数判定用のRubyコードがあったのでコピペしました。敗北感にまみれながら…orz
ミラー-ラビン素数判定法 (Wikipedia)
