当前位置: 首页 > article >正文

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. 排除非质数形式

  • 6k6k 是 6 的倍数,可以被 2 和 3 整除,因此不是质数(除非 k = 1,但 6 也不是质数)。
  • 6k + 26k + 2 = 2(3k + 1),可以被 2 整除,因此不是质数(除非 k = 0,但 2 是质数)。
  • 6k + 36k + 3 = 3(2k + 1),可以被 3 整除,因此不是质数(除非 k = 0,但 3 是质数)。
  • 6k + 46k + 4 = 2(3k + 2),可以被 2 整除,因此不是质数。

因此,除了 6k + 16k + 5,其他形式的数都不是质数。


4. 6k + 56k - 1 的关系

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


5. 结论

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


6. 示例

  • k = 16k - 1 = 5(质数),6k + 1 = 7(质数)
  • k = 26k - 1 = 11(质数),6k + 1 = 13(质数)
  • k = 36k - 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 规则是一个基于数学性质的优化,通过排除非质数形式,减少不必要的计算,从而高效地判断质数。


http://www.kler.cn/a/589388.html

相关文章:

  • 自然语言处理编程文档
  • 数组题型-二分查找-JS
  • 实战:自适应均衡的设计与实现
  • 【Docker】容器中安装cron命令
  • 使用 Docker 部署 MySQL 8
  • TensorFlow 基本原理与使用场景
  • 移除元素(快慢指针)
  • Linux第六讲----git与gdb
  • 文本检测-文本内容审核-文本过滤接口如何用PHP调用?
  • 市长海报/ Mayor‘s posters
  • L2-3 花非花,雾非雾
  • maven使用install将jar包编译到本地仓库管理
  • 【系统架构设计师】操作系统 - 文件管理 ② ( 位示图 | 空闲区域 管理 | 位号 | 字号 )
  • 牛客周赛 Round 85
  • ElementUI 表格中插入图片缩略图,鼠标悬停显示大图
  • 电脑型号与尺寸
  • Leetcode Hot 100 200.岛屿数量
  • 【Agent】OpenManus-Flow-BaseFlow详细分析
  • element-ui progress 组件源码分享
  • 蓝牙技术联盟中国实体成立!华为、小米发声支持本土化战略