素数判断代码中i=i+6与N%(i+2)==0的逻辑原理咨询

这段代码的核心是利用了大于3的素数的分布规律：所有大于3的素数都能表示为 6k ± 1 的形式（k为正整数），这是理解两个问题的关键。

1. 为什么循环步长用 i=i+6？ #

我们可以把所有大于3的整数拆解为以下6种形式：

• 6k、6k+2、6k+4：都是偶数，已经被代码开头的 N%2==0 条件排除
• 6k+3：是3的倍数，也被开头的 N%3==0 条件排除
• 剩下的只有 6k+1 和 6k+5（等价于 6(k+1)-1）这两种可能是素数

所以循环从 i=5（对应 6*1-1）开始，每次加6，就能精准遍历所有可能成为N因子的候选数，跳过那些已经被排除的偶数、3的倍数，大幅减少循环次数，提升判断效率。

2. 为什么要同时检查 N%i==0 和 N%(i+2)==0？ #

刚才提到，可能的素数候选是 6k-1 和 6k+1：

• 当 i=6k-1 时，i+2 正好是 6k+1，这两个是一组相邻的6倍数附近的候选因子
• 代码开头已经排除了2和3的倍数，所以如果N有因子，这个因子必然是 6k±1 中的一个

举个实际例子：判断N=49时，它是7的平方，而7是6*1+1的形式。当循环到i=5时，检查5不能整除49，但检查i+2=7就能发现49%7==0，从而正确返回0（不是素数）。如果只检查i=5，就会漏掉这个因子，导致错误判断。

内容的提问来源于stack exchange，提问作者Hash include