檢查一個數是不是質數

所以我需要解決一個問題，找到驗證以下的第n個數：它是兩個連續素數的總和，它給出了一個整數平方根。我的問題是，eratosthenes篩選使用太多的內存和天真檢查素數太慢。任何方式來解決這個問題，並沒有記憶力？我嘗試過使用Fermat定理，但結果卻變慢了。檢查一個數是不是質數

在此先感謝。

來源

2014-12-13 Andy

這些數字有多大？檢查素數的基本方法是[試驗分割]（http://en.wikipedia.org/wiki/Trial_division），這對於相對較快機器上的小數目來說是足夠的。它可以通過a）奇數除數b）只有素數除數來優化。請參閱[本答案]（http://stackoverflow.com/a/27337333/586873）以獲取插圖。 – 2014-12-13 09:26:13

您可以使用Rabin-Miller進行素性測試。它是概率性的，所以它只告訴你一個數字可能是最好的，但你可以設置確定性的水平。它非常快速，並且對內存要求較低。

顯然你只需要考慮偶數的平方，因爲只有偶數可以是兩個素數的總和（一旦你超過了2）。

來源

2014-12-13 07:59:11

檢查一個數是不是質數

回答

相關問題