c - ふるいなしで素数かどうかを調べる

Question

したがって、次のことを検証する n 番目の数を見つける問題を解決する必要があります。それは 2 つの連続する素数の合計であり、整数の平方根を与えます。私の問題は、エラトステネスのふるいがメモリを使いすぎて、素数の素朴なチェックが遅すぎることです。これを高速かつメモリを追加せずに解決する方法はありますか? フェルマーの定理を使ってみましたが、遅いことがわかりました。

前もって感謝します。

Answer 1

素数性テストには Rabin-Miller を使用できます。これは確率的であるため、数値が素数である可能性が高いことのみを示しますが、確実性のレベルを設定できます。非常に高速で、メモリ要件が低くなります。

偶数だけが 2 つの素数の合計になる可能性があるため (2 を超えると)、偶数の 2 乗だけを考慮する必要があることは明らかです。