素性測試

-2

可能重複：
Fastest primality test 素性測試

有人能給一個高效的算法來確定一個數的素數？

傳統的迭代方法似乎需要大量的時間來測試大數的素數。我已經嘗試了一些概率算法，但不準確。

據我所知，當您使用素數測試時，您將始終在準確性和效率之間進行權衡。我只使用了[米勒拉賓素數測試]（http://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test），但我認爲你需要更多的精確度來處理你正在做的事情。 – Lucas

另外，只需選擇一個足夠大的k。 2^-k（或n> 1的任何n^-k）以指數級快速變化（讀取：非常快）。 –

哇，還有更多的重複 - 只是搜索素性測試。 – Cascabel

關於最有效的概率素性測試是Rabin-Miller primality test（implementation in C）。這是RSA使用的。

如果您需要速度並且在現實世界的應用程序中很少有用，確定性測試更加困難。

2011-11-15 18:34:06 Dennis

回答