Group Group Group Group Group Group Group Group Group

Challenge 2: It’s prime time

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
}

@ahmednagy The function is quite tricky to understand because of its Maths background. Here is what is 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. There are three scenarios to take into account over here:

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

As you can see, each divisor of n which is less than or equal to squareRoot(n) has a correspoding 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) 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!