project euler 58

その他

問題

euler28のように渦巻き状に数を並べていく。
対角線上の数値について、素数の割合が10%以下になる最小の幅を求める。

考え方

幅がiのとき、新たに追加された部分の4つ角の数値は、法則性から
(i-1)*(i-1) - (i-2)
(i-1)*(i-1) - (i-2) + i-1
(i-1)*(i-1) - (i-2) + 2*(i-1)
(i-1)*(i-1) - (i-2) + 3*(i-1)
で求められる。
これの素数を判定し、幅を3,5,7,...として調べていく。