Как проверить, простое ли число

Простое число делится только на 1 и на себя. Проверить это можно перебором делителей.

Идея проверки

Пробуем поделить число на все числа от 2 до n−1. Если нашёлся делитель без остатка — число не простое. Если ни одного не нашлось — простое. Числа меньше 2 простыми не считаются.

n = 13
prostoe = n >= 2
for d in range(2, n):
    if n % d == 0:
        prostoe = False
        break
print(prostoe)   # True

Зачем break

Как только нашли первый делитель, дальше проверять бессмысленно — число уже не простое. break прерывает цикл и экономит время. Это частый и полезный приём.

Можно быстрее

Достаточно проверять делители до квадратного корня из n — большего делителя без меньшего не бывает. Но на старте хватает простого перебора: главное — понять логику.

Частые вопросы

Простое ли число 1? Нет, простые начинаются с 2.

Зачем условие n >= 2? Числа меньше 2 по определению не простые.