language-agnostic - 主要在 O(1) 中测试

Question

我们知道所有素数的形式都是 6k+-1。要检查 n 是否为素数，我们不能将 n 除以 6，取其下限，然后检查加或减 1 是否等于 n？那将检查一个数字是否在恒定时间内是素数，对吗？如果这是真的，为什么其他方法会费心使用筛子进行素性测试？另外，使用这种方法，找到从 2 到 n 的素数范围不会是 O(n) 吗？那么这种方法比埃拉托色尼筛法快吗？

Answer 1

是的，所有素数都是 6k +/- 1 的形式，但这并不意味着 6k +/- 1 形式的每个数字都是素数。考虑 25，即 6 * 4 + 1。显然，25 不是素数。

Answer 2

我们知道所有素数的形式都是 6k+-1。

但并非所有 6k+-1 形式的数字都是素数。（例如 6 * 4 + 1 = 25）

这意味着您的 isPrime 基于此测试将给出误报（例如 25）。不过，它永远不会给出假阴性，因此在您应用真正的素性测试之前，它可以用来排除一些可能性。

您可能会发现https://en.wikipedia.org/wiki/Primality_test#Simple_methods 具有教育意义。特别是，6k+1 模式只是可用于创建朴素素性测试的众多模式之一，更一般/优化的情况最终会减少到……埃拉托色尼筛。

Answer 3

这可行，但实用程序很小。本质上，这个陈述等同于“如果一个数不能被 2 或 3 整除，它可能是素数”。

6k 可被 6 整除（冗余检查 - 与可被 2 或 3 整除相同）。
6k + 1 可能是素数
6k + 2 = 2(k+3) 可以被 2 整除
6k + 3 = 3(k+2) 可以被 3 整除
6k + 4 = 2(3k + 2) 可以被 2 整除（冗余检查）
6k + 5 可能是素数。（对于 m = k+1，相当于 6m - 1）

所以我们实际完成的是用 2、3 代替试除法，（并消除倍数，筛分法）用两个稍微复杂的操作。这意味着该方法是Eratosthenes 筛的前两次迭代。

所以任何使用这个属性的算法都等价于下面的代码：

boolean isPrime(n)
{
    if (n % 2 == 0) return false;
    if (n % 3 == 0) return false;
    return isPrimeRigourousCheck(n);
}

这是非常基本的，并且比解其他方程 2 次要简单得多。

有趣的是，我们可以构建其他类似的规则。例如，明显的下一个选择是

30k +- (1,7,11,13) 但这给了我们 8 个案例要解决，相当于添加了单个试验除法：

if (n % 5 == 0) return false;  

到上面的代码。（这是一个 3 次迭代筛）