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

CodePudding user response：

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.

CodePudding user response：

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.