Осваиваем задачу: проверка числа на простоту
Разберём задачу, которая встречается практически в каждом учебнике по программированию.
Задача
Определить, является ли число 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) по памяти.
Такой пример хорошо закрепляется практикой — перепишите решение руками и прогоните на своих тестах.
Related:
Два способа решения: сумма цифр числа
Два подхода: быстрая сортировка