A step-by-step look at primality testing (part 1eb4)

Пройдём задачу шаг за шагом — такой формат удобен для первого знакомства с алгоритмами.

Задача

Определить, является ли число 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. Результат. Убеждаемся, что возвращаемое значение соответствует условию задачи, включая крайние случаи.

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

Читайте также:

самый · задачу · находит · простым · следим · корня · Убеждаемся · какие · числа · переменных · корректными · считаются · Определить · способ · range(2 · включая · Именно · квадратного · мысленный · повторите · изменениями · Входные · каждой · Читая · Результат · памяти · итерации · Проверяем · разбор