Почему этот простой тест работает?

Question

Я нашел эту функцию Python для проверки, является ли число простым; однако я не могу понять, как работает алгоритм.

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

Начнем с первых четырех строк кода функция в:

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 

Функциональные тесты, чтобы увидеть, если n равно 2 или 3 первой. Поскольку они оба являются простыми числами, функция возвращает True, если n равно.

Затем функция проверяет, делится ли n на 2 или 3 и возвращает False, если это либо значение true. Это исключает чрезвычайно большое количество случаев, потому что половина всех чисел выше двух не являются простыми числами - они делятся на 2. Такая же причина относится к тестированию на делимость на 3 - она ​​также исключает большое количество случаев.

сложнее часть функции находится в следующих строках:

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

    i += w 
    w = 6 - w 

return True 

первых, i (или индекс) установлен в положение 5. 2 и 3 уже были испытаны, и 4 был протестирован с n % 2 , Таким образом, имеет смысл начать с 5.

Далее, w установлено в 2. w, кажется, является «приращением». К настоящему времени, функция испытала для всех четных чисел (n % 2), так что это будет быстрее увеличиваться на 2.

Функция входит в while цикл с условием i * i <= n. Этот тест используется, потому что every composite number has a proper factor less than or equal to its square root. Было бы нецелесообразно проверять числа после квадратного корня, потому что это было бы излишним.

В цикле while, если n делится на i, то это не является простым и функция возвращает False. Если это не так, i увеличивается с помощью «инкрементера» w, что, опять же, быстрее.

Возможно, самая сложная часть функции находится во второй-последней строке: w = 6 - w. Это приводит к тому, что «incrementer» w переключается между значениями 2 и 4 с каждым прохождением через цикл. В случаях, когда w равно 4, мы обходим число, делящееся на 3. Это быстрее, чем остальное на 2, потому что функция, уже проверенная на делимость как на 2, так и на 3.

И наконец, функция возвращает True. Если функция не обнаружила случаев, когда n делится чем-то, то это должно быть простое число.

Answer 2

За исключением 2 и 3 все простые числа могут представлять собой (6 * n) +1 или (6 * n) -1, где n равно 0 до бесконечности. Эта программа работает в соответствии с этой идеей. Используя эти строки проверить число может делящиеся на 2 или 3

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

Затем нам нужно проверить число может делящиеся на других простых чисел терке, чем 3.

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

    i += w 
    w = 6 - w 

На следующий простое число 5. Поэтому начальное значение I, как установлено 5. Для того, чтобы получить все числа в наборе (6 * п) +1, или (6 * N) -1 в качестве альтернативы изменить значение w (2,4). И этот фрагмент используется для проверки квадратного корня из числа.

while i * i <= n: 

Этот код не является эффективным, так как некоторые не простые числа в наборе (6 * п) +1 или (6 * п) -1.