algorithm - 有效地找到前 n 个素数

Question

我有一个蛮力算法，它接受输入 n，并显示前 n 个素数。代码有效，但我还必须回答这个问题:

Give the number of test items that would be required to assure correctness.

有没有办法计算这个？我在技术上是否需要测试每个可能的 int 值(所有 20 亿种可能性)？

Answer 1

如果您有一个数字n，并且需要检查它是否是质数，那么有比蛮力更有效的方法。

一种方法是使用 Miller-Rabin Primality Test . Miller-Rabin 测试要么找到一个数是合数的证据，要么找不到这样的证据(它不直接证明一个数是素数)。所以计划是:

1. 最多运行 Miller-Rabin k 次(或直到它发现数字是合数)

2. 如果 Miller-Rabin 声称它是一个可能的素数，则执行暴力检查

Miller-Rabin 跑 as follows .显然，您只需要测试奇数 n，因此 n - 1 是偶数，您可以写成 n - 1 = 2^sd 对于一些正的 s 和正的奇数 d。从 (0, n - 1) 范围内随机选择一个 a。如果 a^d ≠ 1 | n 和 a^2rd ≠ -1 | n，则n是合数。

如果 n 是复合，则 Miller-Rabin 的 k 次迭代无法证明它的概率小于 4^-k 。请注意，通过 Prime Number theorem , 素数稀缺。

k Miller-Rabin 应用程序的计算复杂性，即使是简单的实现，is , 是 O(k log³(n))。