6k ± 1 规则

6k ± 1 规则 是基于对质数分布规律的观察和数学证明得出的。它指出，除了 2 和 3 之外，所有质数都可以表示为 6k ± 1 的形式，其中 k 是正整数。以下是详细的证明过程：

---

1. 质数的基本性质

质数是指大于 1 的自然数，且只能被 1 和它本身整除的数。质数的分布规律与模 6 的余数密切相关。

---

2. 模 6 的余数分析

任何整数 n 除以 6 的余数只能是 0, 1, 2, 3, 4, 5。因此，n 可以表示为以下形式之一：

• 6k（余数为 0）
• 6k + 1（余数为 1）
• 6k + 2（余数为 2）
• 6k + 3（余数为 3）
• 6k + 4（余数为 4）
• 6k + 5（余数为 5）

---

3. 排除非质数形式

• 6k：6k 是 6 的倍数，可以被 2 和 3 整除，因此不是质数（除非 k = 1，但 6 也不是质数）。
• 6k + 2：6k + 2 = 2(3k + 1)，可以被 2 整除，因此不是质数（除非 k = 0，但 2 是质数）。
• 6k + 3：6k + 3 = 3(2k + 1)，可以被 3 整除，因此不是质数（除非 k = 0，但 3 是质数）。
• 6k + 4：6k + 4 = 2(3k + 2)，可以被 2 整除，因此不是质数。

因此，除了 6k + 1 和 6k + 5，其他形式的数都不是质数。

---

4. 6k + 5 与 6k - 1 的关系

注意到 6k + 5 可以改写为 6(k + 1) - 1，即 6k - 1。因此，6k ± 1 包含了所有可能的质数形式。

---

5. 结论

除了 2 和 3 之外，所有质数都可以表示为 6k ± 1 的形式，其中 k 是正整数。

---

6. 示例

• k = 1：6k - 1 = 5（质数），6k + 1 = 7（质数）
• k = 2：6k - 1 = 11（质数），6k + 1 = 13（质数）
• k = 3：6k - 1 = 17（质数），6k + 1 = 19（质数）

---

7. 代码实现

基于 6k ± 1 规则的质数判断算法：

bool isPrime(int n) {if (n <= 1) return false;if (n <= 3) return true; // 2 和 3 是质数if (n % 2 == 0 || n % 3 == 0) return false; // 排除 2 和 3 的倍数for (int i = 5; i * i <= n; i += 6) { // 只检查 6k ± 1 的数if (n % i == 0 || n % (i + 2) == 0) return false;}return true;
}

---

8. 优化意义

通过 6k ± 1 规则，可以将需要检查的除数数量减少到原来的 1/3，从而显著提高算法效率。

---

总结

6k ± 1 规则是一个基于数学性质的优化，通过排除非质数形式，减少不必要的计算，从而高效地判断质数。