啓發式 - 是否是素數？

我從標準輸入讀取一個正整數N，我試圖找出N是否是一個素數。啓發式 - 是否是素數？

我知道我可以將N除以所有正數直到sqrt（N），但這很耗時，而且我的算法會不時給出誤報，所以我正在尋找一種啓發式方法來解決這個問題。我記得去年我學習了一個拼貼算法，它會選擇一個數字，然後檢查N是否可以被這個數字（或者它的因子）整除，如果不是，那麼它可以告訴N是一個素數，但它在大約1/40的時間內會錯誤地將其識別爲黃金。

有人認識到我說的這個算法嗎？指向它的鏈接將非常有幫助。

來源

2012-12-12 Ionut Hulub

爲什麼你需要這麼快？你在優化什麼？ –

@Diego Basch：我正在優化面試:) –

查看http://en.wikipedia.org/wiki/Solovay-Strassen_primality_test - 順便說一下，這是一個糟糕的面試問題。有人真的問過了，或者你認爲它可能會出現？ –

嗯，有幾個概率algorithsm，有的在wikipedia page描述，很有可能你正在談論 ~~Miller-Rabin~~ Fermat Primality Test

注意，自2002年以來存在實際上是一個O（日誌（N）^ 6）確定性的方法來確定一個數是否爲素 - 被稱爲AKS（它的開發之後）

這是一個有趣的問題 - 許多人認爲素性測試不能在輸入的大小上進行多項式（即，在n對數）和確定性，但他們的方法顯示，否則。

來源

2012-12-12 07:06:33 amit

其實我在談論我在你的幫助下找到的費馬素性測試。我會盡可能接受你的答案。 –

啓發式 - 是否是素數？

回答

相關問題