在素数测试中，我不明白为什么我们将 i 增加 6 (i=i+6)？以及 for 循环块中的 if 语句条件？

Question

我需要一些帮助！！这是我在数据结构书中创建的代码我知道所有素数都是 6k ± 1 的形式，除了 2 和 3，其中 k 是某个整数。问题出在 for 循环中，为什么我们将 6 添加到 i (i+6) 以及 if 语句中的此条件 if (n%i == 0 || n%(i+2) == 0):

function isPrime(n){
if (n <= 1) return false;
if (n <= 3) return true;

// This is checked so that we can skip
 // middle five numbers in below loop
if (n%2 == 0 || n%3 == 0) return false;

for (var i=5; i*i<=n; i=i+6){
    if (n%i == 0 || n%(i+2) == 0)
    return false;
}
    
    return true;
}

Answer 1

算法说素数可以是 6k+1 或 6k-1.

的形式

让我们假设这里的 k 是 1，那么质数是 5 和 7。所以在循环的第一次迭代中，这个条件就是这样：

if (n%i == 0 || n%(i+2) == 0)

n%5 或 n%7。

现在下一个 i 是 11。所以条件变成， n/11==0 或 n/13==0。 11 和 13 的形式分别为 6k-1 和 6k+1。

这就是为什么每次都需要增加 6 以及这两个条件。

Answer 2

首先，它正在检查 0(mod2) 和 0(mod3)，我们知道连续 2 个数字中的任何一个都可以被 2 和连续 3 个数字中的任何一个整除能被3整除，其他必须能被2整除

因此，仅当数字不能被 2 或 3 整除且 >=25 时，for 循环才会开始。跳过计数背后有简单的数学运算。
所有整数都可以表示为6k+m，其中m ε {0, 1, 2, 3, 4, 5}，k是某个整数。 事实上，它的基础来自于所有整数都可以用 3k,3k+1,3k+2 的形式表示的事实。

这是显而易见的。因此：

m=0: 6k能被6整除。不是素数

m=1: 6k+1没有直接因素。可能是素数。

m=2: 6k+2 = 2 x (3k+1)。不是质数

m=3: 6k+3 = 3 x (2k+1)。不是质数

m=4: 6k+4 = 2 x (3k+2)。不是质数

m=5: 6k+5 没有直接因数。可能是素数

但是 6k+5=6k-1 (mod 6), 所以只有两个可能的素数是 6k+1 和 6k-1.

Answer 3

感谢@SebastianSimon 澄清这一点 “只需要检查 6 的倍数（两次：一次是 6k − 1，一次是 6k + 1）” 这是重构后的代码更易读，并解释每一步。

function isPrime(n){
//one is not primary number
if (n <= 1) return false;
//3 and 2 is a primary number 
if (n <= 3) return true;
//Any number that is divisible by 2 and 3 
//other than the number 2 and 3  is not prime
if (n%2 == 0 || n%3 == 0) return false;

// all primes are of the form 6k ± 1, with the exception of 2 and 3
// where k is some integer,
//so only multiples of 6 need to be checked 
//(twice: once for 6k − 1, once for 6k + 1)
//that is the reason why we increase i by 6 (i=i+6) in the for loop.

// the loop only has to test until the square root of n so (i*i<=n)
// This is because if the square root of n is not a prime number,
// n is not a 
// prime number by mathematical definition. 

for (var i=6; i*i<=n; i=i+6){
    //Divisibility test by 6k+1 and 6k-1
    if (n%(i+1) == 0 || n%(i-1) == 0)
    return false;
}
    
    return true;
}

在素数测试中，我不明白为什么我们将 i 增加 6 (i=i+6)？以及 for 循环块中的 if 语句条件？

in Primality Test ,i do not understand why we increase i by 6 (i=i+6) ? and the if statment conditions in the for loop block?

javascript

algorithm

data-structures

primality-test