Evan Mosseri - 8 months ago 37

Python 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

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.