Why does this simple test work?

Question

I found this Python function to check if a number is prime; however, I cannot understand 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 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 checks if n matches 2 or 3. Since they are both prime numbers, the function returns True if n is equal.

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

The more complex part of the function is in the following 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 the index) is set to 5. 2 and 3 have already been tested, and 4 with n % 2 . So, it makes sense to start with 5.

Then w set to 2. w seems to be an "increment". To date, the function has checked all even numbers ( n % 2 ), so it would be faster to increase by 2.

The function enters the while with the condition i * i <= n . This test is used because each composite number has its own coefficient less than or equal to its square root . It would be impractical to check the numbers after the square root, because that would be superfluous.

In a while , if n is divisible by i , then it is not simple and the function returns False . If this is not the case, i incremented using the "incrementer" w , which, again, is faster.

Perhaps the most difficult part of the function lies in the second or last line: w = 6 - w . This causes the incrementer w switch between the values ​​2 and 4 with each passage of the loop. In cases where w is 4, we bypass the number divisible by 3. This is faster than remaining by 2, because the function has already been tested for divisibility by both 2 and 3.

Finally, the function returns True . If the function has not found cases when n is sharing something, then this should be a prime number.

Answer 2

With the exception of 2 and 3, all primes can be (6 * n) +1 or (6 * n) -1, where n is 0 to infinity. This program works in accordance with this idea. Using these lines, the check number can be divided by 2 or 3

  if n % 2 == 0: return False if n % 3 == 0: return False 

Then we need to check that the number can be divided by other prime numbers, greater than 3.

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

The next prime number is 5. Therefore, the initial value of i is set to 5. To get the whole number in the set (6 * n) +1 or (6 * n) -1, alternatively change the value of w (2,4). And this fragment is used to check the square root of a number.

  while i * i <= n: 

This code is inefficient because some non-prime numbers in the set (6 * n) +1 or (6 * n) -1.