CODEWITHSUNDEEP
javascriptalgorithmfunctionloops
fred c.
fred c.

Reputation: 31

Determine a prime number function

Could anyone explain to me the 2nd and 3rd statement in the for loop

What is the 1st and 2nd i in the middle part and the last one (i = i + 6)

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

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

      return false;
  }
  return true
}

console.log(prime(11))
console.log(prime(25))
console.log(prime(29))

Upvotes: 1

Views: 62

Answers (1)

vish4071
vish4071

Reputation: 5277

There are a couple of hacks in this function to determine primality of a number n.

  1. Every non-prime number has at-least 1 factor less than or equal to its square root.
  2. Every 6th number from 3 onwards is a multiple of 3. So, if we have already checked that 3 does not divide n, we can safely say numbers like 9,15,21... will not divide n.

The if inside the loop checks for divisibility of n by i or i + 2. Since we know, 3 | i+4 (-- from 2 above), we don't check divisibility there as it is not required. And since this loop runs from i = 5 upto i = sqrt(n), if we find no factors, we can exit the loop and return true for number's primality (-- from 1 above)

Upvotes: 1

Related Questions