javascriptalgorithmdata-structuresprimality-test

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

Solution

  • 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.