inamori’s diary

n2 + 1という形の素数を求める問題はProject Eulerで頻出なので簡単なアルゴリズムを解説します。 例として200以下のこの形の素数を列挙します。 まず、n2 + 1を順に並べます。 2 5 10 17 26 37 50 65 82 101 122 145 170 1972で割り切れる数が1つおきにあるので、それを最初だけ残して2で割ります。 2 5 5 17 13 37 25 65…