0

一个月以来，我一直在阅读一本具有竞争力的编程书籍。这本书是由我国（孟加拉国）的世界决赛选手之一撰写的。需要指出的是，这本书是用我们的母语（孟加拉语）写的，在世界范围内并不那么受欢迎。因为有孟加拉语的内容，我不能在这里引用它。这就是为什么我首先感到抱歉。

在那本书的数论章节中，给出了许多算法来测试素性。他展示的最优化的是 O(nloglogn) 中的“Eratosthenes 筛”。但他写了一行。我正在翻译它。“有一种更有效的方法来测试 O(logn) 中的素数。自己想一想。如果你没有完成，那就用谷歌搜索吧！！”

我用谷歌搜索了它。但我没有找到任何令人满意的东西。

真的可以在 O(logn) 中测试一个数字的素数吗？如果有可能，那么可以得出哪个范围？

4

1 回答 1

5

该说法不正确。对于数字 N，位数是O(log N)，因此该语句意味着存在一种算法，该算法在位数上是线性的。最著名的结果是位数的多项式。（Agrawal-Kayal-Saxena 素性检验，Õ(logN 12 )。这是 logN 的 12 次方，而不是 1。

尽管如此，Õ(logN 12 ) ⊂ O(N)

于 2019-06-25T11:02:43.040 回答