n**2+1の素数判定を2次ふるいで行う - Qiita

\begin{align} &nが2 \le n \le Nの整数の時 \ \ (N=10^7) \\ &f(n) = n^2+1 が素数になる個数を求めよ \\ \end{align} pythonではsympyを使えば一行で書け速度もそこそこですがわずかに1分をオーバーしました。今回はこれを2次ふるい法と呼ばれるアルゴリズムを使って解いてみたいと思います。 from sympy import isprime N = 10**7 print(sum([isprime(n**2 + 1) for n in range(N+1)])) # 456361 2次ふるい法 （Quadratic sieving） ここで紹介する「2次ふるい法」は一般に素因数分解で使われるものとは異なり、2次式で「エラトステネスのふるい」のように合成数を除いて行って素数だけが残るようにするアルゴリズムです。詳細は以