我有一个蛮力算法,它接受输入 n,并显示前 n 个素数。代码有效,但我还必须回答这个问题:
Give the number of test items that would be required to assure correctness.
有没有办法计算这个?我在技术上是否需要测试每个可能的 int 值(所有 20 亿种可能性)?
最佳答案
如果您有一个数字n,并且需要检查它是否是质数,那么有比蛮力更有效的方法。
一种方法是使用 Miller-Rabin Primality Test . Miller-Rabin 测试要么找到一个数是合数的证据,要么找不到这样的证据(它不直接证明一个数是素数)。所以计划是:
最多运行 Miller-Rabin k 次(或直到它发现数字是合数)
如果 Miller-Rabin 声称它是一个可能的素数,则执行暴力检查
Miller-Rabin 跑 as follows .显然,您只需要测试奇数 n,因此 n - 1 是偶数,您可以写成 n - 1 = 2sd 对于一些正的 s 和正的奇数 d。从 (0, n - 1) 范围内随机选择一个 a。如果 ad ≠ 1 | n 和 a2rd ≠ -1 | n,则n是合数。
如果 n 是复合,则 Miller-Rabin 的 k 次迭代无法证明它的概率小于 4-k 。请注意,通过 Prime Number theorem , 素数稀缺。
k Miller-Rabin 应用程序的计算复杂性,即使是简单的实现,is , 是 O(k log3(n))。
关于algorithm - 有效地找到前 n 个素数,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/40077420/