I have found this Python function for testing whether or not a number is prime; however, I cannot figure out how the algorithm works.
"""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:
i += w
w = 6 - w
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
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
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.
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.
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.