主要在 O(1) 中测试

Question

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

Answer 1

We know that all prime numbers are of the form 6k+-1.

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

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

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

Answer 2

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

Answer 3

这可行，但实用性很小。本质上，这个语句等同于 "If a number is not divisible by 2 or 3, it might be prime."

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 的试验除法（并消除倍数，明智地筛选）。这意味着这个方法是埃拉托色尼筛法的前两次迭代。

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

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 次迭代筛）

主要在 O(1) 中测试

Primarily Test in O(1)

language-agnostic

primality-test