二元搜索可用於檢查素數嗎？

我不知道是否可以使用二進制搜索來檢查一個數是否爲素數，因爲真正的問題是我可以找到一個除了數字本身和1之外還可以除數的數字，因此我可以想象通過一個有序數組整數從2到i/2（我是一個正在檢查的數字）.......二元搜索可用於檢查素數嗎？

2011-09-24 M.K

我從來沒有聽說過這樣的算法。所以我的猜測是不。 – Mysticial

初看起來，這幾乎毫無意義。但也許我錯過了一些東西。 – Joey

順便說一句，如果你正在尋找我的除數，候選人將是2到sqrt（i），而不是2到i/2 –

顯然不是。

二元搜索是一種將區間分成兩個（幾乎）相等的部分並決定哪一個包含搜索值的方法。

測試任何數字以查看它是否是除數不會告訴您任何有關選擇哪個間隔的內容。

2011-09-24 16:55:00

我明白了，我只是認爲必須有某種選擇間隔的方式，但我猜不是 –

@ M.K。如果有一些有用的*方法來選擇區間（據我所知，沒有人證明這種方法不存在），那麼爲什麼這種方法不能應用於內部2，sqrt（n） - 解決問題一步到位。（*有很多無用的方法，例如強力選擇間隔。） – emory

回答