'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?

i need some help please !! this is the code i founded in data-strucure book i understand that t all primes are of the form 6k ± 1, with the exception of 2 and 3 where k is some integer. the problem is in the for loop why we add 6 to i (i+6) and this condition in if statment 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;
}
javascriptalgorithmdata-structuresprimality-test


Solution 1:[1]

The algo says a prime number can be of the form 6k+1 or 6k-1.

Let us assume k is 1 here, then the prime is 5 and 7. So in the first iteration of the loop, this condition does exactly that:

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

n%5 or n%7.

Now next i is 11. So the condition becomes, n/11==0 or n/13==0. Both 11 and 13 are of the form 6k-1 and 6k+1 respectively.

That is why you need an increment of 6 everytime and those two conditions.

Solution 2:[2]

firstly, it is checking for 0(mod2) and 0(mod3), we know any one of consecutive 2 numbers are divisible by 2 and any one of 3 consecutive number are divisible by 3 and other must be divisible by 2

  • so, the for loop starts only if number is not divisible by 2 or 3 and it is >=25. And skip count has simple math behind it.
  • All integers can be represented as 6k+m, where m ? {0, 1, 2, 3, 4, 5}, and k is some integer. In fact the base of this comes from the fact that all integers can be represented in form of 3k,3k+1,3k+2.

This is obvious. Therefore:

m=0: 6k is divisible by 6. Not prime

m=1: 6k+1 has no immediate factors. May be prime.

m=2: 6k+2 = 2 x (3k+1). Not prime

m=3: 6k+3 = 3 x (2k+1). Not prime

m=4: 6k+4 = 2 x (3k+2). Not prime

m=5: 6k+5 has no immediate factors. May be prime

  • But 6k+5=6k-1 (mod 6), so only two prime possible are 6k+1 and 6k-1.

Solution 3:[3]

thanks for clarify that point by @SebastianSimon "only multiples of 6 need to be checked (twice: once for 6k ? 1, once for 6k + 1)" this is the code after refactor it to be more readable with explain every step.

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;
}

Sources

This article follows the attribution requirements of Stack Overflow and is licensed under CC BY-SA 3.0.

Source: Stack Overflow

Solution Source
Solution 1 Tushar Shahi
Solution 2 Andronicus
Solution 3 MOHAMMADE

Related Questions