Пошаговый разбор: проверка числа на простоту
Медленный разбор помогает понять код, а не просто скопировать его.
Задача
Определить, является ли число n простым. Достаточно проверять делители до квадратного корня из n.
Решение
def is_prime(n: int) -> bool:
if n < 2:
return False
for d in range(2, int(n ** 0.5) + 1):
if n % d == 0:
return False
return True
print(is_prime(29))
Как это работает
Если у числа есть делитель, больший корня, то у него есть и парный меньший. Поэтому перебор до √n гарантированно находит любой составной делитель.
Пример работы
True
Сложность
O(√n) по времени, O(1) по памяти.
Разбор по шагам
1. Шаг 1. Входные данные. Проверяем, что приходит в функцию, и какие значения считаются корректными. 2. Шаг 2. Основной цикл. Именно здесь происходит вся работа; следим за изменениями переменных на каждой итерации. 3. Шаг 3. Результат. Убеждаемся, что возвращаемое значение соответствует условию задачи, включая крайние случаи.
Когда каждый шаг понятен, доработка решения перестаёт быть лотереей.
Related:
Пошаговый разбор: проверка числа на простоту
Разбираем задачу: быстрая сортировка
Медленно и подробно: удаление дубликатов из списка