Why does this prime test work?

Question

I have found this Python function for testing whether or not a number is prime; however, I cannot figure out how the algorithm works.

def isprime(n):
   """Returns True if n is prime"""
   if n == 2: return True
   if n == 3: return True
   if n % 2 == 0: return False
   if n % 3 == 0: return False

   i = 5
   w = 2
   while i * i <= n:
      if n % i == 0:
         return False

      i += w
      w = 6 - w

   return True

Answer 1

Let's start with the first four lines of the function's code:

def isprime(n):
    if n == 2: return True
    if n == 3: return True
    if n % 2 == 0: return False
    if n % 3 == 0: return False

The function tests to see if n is equal to 2 or 3 first. Since they are both prime numbers, the function will return True if n is equal to either.

Next, the function tests to see if n is divisible by 2 or 3 and returning False if either is true. This eliminates an extremely large amount of cases because half of all numbers above two are not primes - they are divisible by 2. The same reason applies to testing for divisibility by 3 - it also eliminates a large number of cases.

The trickier part of the function is in the next few lines:

i = 5
w = 2
while i * i <= n:
    if n % i == 0:
        return False

    i += w
    w = 6 - w

return True

First, i (or index) is set to 5. 2 and 3 have already been tested, and 4 was tested with n % 2. So, it makes sense to start at 5.

Next, w is set to 2. w seems to be an "incrementer". By now, the function has tested for all even numbers (n % 2), so it would be faster to increment by 2.

The function enters a while loop with the condition i * i <= n. This test is used because every composite number has a proper factor less than or equal to its square root. It wouldn't make sense to test numbers after the square root because it would be redundant.

In the while loop, if n is divisible by i, then it is not prime and the function returns False. If it is not, i is incremented by the "incrementer" w, which, again, is faster.

Perhaps the trickiest part of the function lies in the second-to-last line: w = 6 - w. This causes the "incrementer" w to toggle between the values 2 and 4 with each pass through loop. In cases where w is 4, we are bypassing a number divisible by 3. This is faster than remaining at 2 because the function already tested for divisibility by both 2 and 3.

Finally, the function returns True. If the function hasn't detected any cases where n is divisible by something, then it must be a prime number.