Evan Mosseri - 5 months ago 18x
Python Question

# Why does this prime test work?

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
``````

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.

Source (Stackoverflow)