Как это python l oop проверяет простоту, если оно зацикливается меньше числа n?

Question

Привет, ребята, поэтому мне было интересно, как этот код:

def is_prime(n):
    for i in range(2, int(n**.5 + 1)):
        if n % i == 0:
            return False
    return True

может проверять простое число, когда в строке 2: for i in range(2, int(n**.5 + 1)): диапазон не: range(2, n)? Разве ему не нужно перебирать каждое число до n, но исключая его? Этот не делает этого, но каким-то образом он работает ... Может кто-нибудь объяснить, почему это работает, пожалуйста.

Answer 1

Поскольку при разложении на простые множители любого числа n (пробным делением) необходимо проверять только простые числа до sqrt(n)

.. Кроме того, пробная Для факторов требуется go не далее sqrt(n), потому что, если n делится на некоторое число p, тогда n = p × q и если q было меньше p, n было бы обнаружено раньше как делимое на q или на простой множитель q.

Кстати, пробное деление медленно проверяет простоту или возможную простоту. Существуют более быстрые вероятностные c тесты, такие как тест Миллера-Рабина , которые могут быстро проверить, является ли число составным или, вероятно, простым.

Answer 2

l oop выполняет итерацию по всем числам от 2 до квадрата root на n. Для любого делителя, который он может найти выше этого квадрата root (если он продолжит итерацию до n - 1), очевидно, что под ним будет другой делитель.