Challenge 2: It’s prime time

[ahmednagy]

Can someone explain how this function works please?

func isPrime(_ number: Int) -> Bool {
  if number < 0 {
    return false
  }
  
  /*
   We handle these cases up front because we want to make sure the range 2...root (used below) is valid, which is the case only when root >= 2, so for numbers >= 4.
   */
  if number <= 3 {
    return true
  }

  let doubleNumber = Double(number)
  let root = Int(doubleNumber.squareRoot())
  for divisor in 2...root {
    if isNumberDivisible(number, by: divisor) {
      return false
    }
  }
  return true
}

[shogunkaramazov]

@ahmednagy The function is quite tricky to understand because of its Maths background. Here is what is actually going on under the hood in this case.

If a is a divisor of n then a * b = n where b is another divisor of n since b * a = n as well so a = n / b and b = n / a because of that. There are six different scenarios to take into account over here as follows:

1. a = squareRoot(n) so b = n / a hence b = n / squareRoot(n) thus b = squareRoot(n) since squareRoot(n) * squareRoot(n) = n.

2. a < squareRoot(n) so 1 / a > 1 / squareRoot(n) hence n / a > n / squareRoot(n) thus b > squareRoot(n).

3. a > squareRoot(n) so 1 / a < 1 / squareRoot(n) hence n / a < n / squareRoot(n) thus b < squareRoot(n).

4. b = squareRoot(n) so a = n / b hence a = n / squareRoot(n) thus a = squareRoot(n) since squareRoot(n) * squareRoot(n) = n.

5. b < squareRoot(n) so 1 / b > 1 / squareRoot(n) hence n / b > n / squareRoot(n) thus a > squareRoot(n).

6. b > squareRoot(n) so 1 / b < 1 / squareRoot(n) hence n / b < n / squareRoot(n) thus a < squareRoot(n).

As you can see, each and every divisor of n which is less than or equal to squareRoot(n) has a corresponding divisor of n which is greater than or equal to squareRoot(n).

So it definitely makes perfect sense in this case to actually only check the divisors of n which are less than or equal to squareRoot(n) in order to optimize the prime numbers algorithm implementation.

Please let me know if you have any more questions or other issues about the whole thing when you get a chance. Thank you!