Работа с циклами обычно сводится к двум сценариям:
- Агрегация. Накопление результата во время итераций и работа с ним после цикла. Переворот строки относится к такому варианту
- Выполнение цикла до достижения необходимого результата и выход. Например, задача поиска простых чисел — которые делятся без остатка только на себя и на единицу.
Рассмотрим алгоритм проверки простоты числа. Будем делить искомое число x
на все числа из диапазона от двух до x - 1
и смотреть остаток. Если в этом диапазоне не найден делитель, который делит число x
без остатка, значит, перед нами простое число.
Проверка простоты числа 5 — по шагам
- Берём число x = 5. Возможные делители ищем в диапазоне от 2 до x - 1, то есть от 2 до 4.
- Делим 5 на 2. Остаток равен 1, делителя не нашли, продолжаем.
- Делим 5 на 3. Остаток равен 2, делителя не нашли, продолжаем.
- Делим 5 на 4. Остаток равен 1, делителя не нашли, завершаем перебор.
Итог. В диапазоне 2…4 не нашлось ни одного числа, на которое 5 делится без остатка. Следовательно, 5 — простое число.
В этом случае достаточно проверять числа не до x - 1
, а до половины числа. Например, 11 не делится на 2, 3, 4, 5. Но и дальше не будет делиться на числа больше своей половины. Значит, можно оптимизировать алгоритм и проверять деление только до x / 2
:
def is_prime(number: int) -> bool:
if number < 2:
return False
divider = 2
while divider <= number / 2:
if number % divider == 0:
return False
divider += 1
return True
print(is_prime(1)) # => False
print(is_prime(2)) # => True
print(is_prime(3)) # => True
print(is_prime(4)) # => False
Если быть честными до конца, то для решения задачи хватит проверки чисел до значения квадратного корня number
, но в нашем случае важно сосредоточиться на понимании работы с условиями внутри цикла
Представим, что по алгоритму последовательного деления на числа до x / 2
нашлось одно, которое делит без остатка. Значит, переданный аргумент — не простое число, и дальнейшие вычисления не имеют смысла. В этом месте стоит возврат False
.
Если цикл отработал целиком, и не нашлось число, которое делит без остатка, значит, число — простое.