Проверка на простоту числа с помощью Python

Для проверки простоты числа в Python, можно использовать следующий код:

python
def is_prime(n):
    if n <= 1:
        return False
    elif n <= 3:
        return True
    elif n % 2 == 0 or n % 3 == 0:
        return False
    i = 5
    while i * i <= n:
        if n % i == 0 or n % (i + 2) == 0:
            return False
        i += 6
    return True

Функция `is_prime()` принимает на вход целое число `n` и возвращает `True`, если оно является простым и `False` в противном случае.

Алгоритм проверки простоты основан на теореме о том, что все простые числа, кроме 2 и 3, имеют вид 6*k ± 1. Таким образом, в цикле проверяются только числа такого вида, что значительно сокращает количество итераций.

Пример использования:

python
print(is_prime(7))   # True
print(is_prime(12))  # False

Также можно использовать более простой, но менее эффективный алгоритм проверки простоты, основанный на переборе делителей:

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

Этот алгоритм перебирает все числа от 2 до квадратного корня из `n` и проверяет, делится ли `n` на них без остатка.

Пример использования:

python
print(is_prime(7))   # True
print(is_prime(12))  # False

Оба алгоритма являются достаточно эффективными для проверки простоты чисел меньше 10^9. Однако, для больших чисел может потребоваться использование более сложных алгоритмов.