Упражнения по Python для начинающих

Проверка числа на простоту в Python

В этом уроке вы проверите, является ли число простым, перебирая делители только до его квадратного корня.

  • Начальный
  • Чтение: 2 мин
  • Примеров для запуска: 1

Введение

Какую задачу это решает

Простые числа стоят за шифрованием в интернете, хеш-таблицами и множеством головоломок. Проверка на простоту перебором всех делителей до самого числа работает для 29, но становится мучительно медленной для больших чисел. Одно небольшое наблюдение делает проверку гораздо быстрее.

Пример из жизни

Поиск делителей похож на попытку выложить плитку сплошным прямоугольником. 36 плиток укладываются как 1×36, 2×18, 3×12, 4×9 и 6×6. После квадрата (6×6) те же прямоугольники повторяются, только повёрнутые, поэтому дальше квадратного корня искать нечего. 29 плиток укладываются только как 1×29, значит, 29 простое.

От прямоугольников из плитки к коду
number > 1🚪 Простыми могут быть только числа больше 1
divisor * divisor <= number🪞 Остановиться на квадрате: дальше одни повторы
number % divisor == 0🔍 Сплошной прямоугольник получился: число не простое
divisor += 1➡️ Попробовать следующую ширину
Если до квадратного корня делитель не найден, число простое.
Одним предложением

Простое число - целое число больше 1, у которого только два положительных делителя: 1 и оно само.

Главное

  1. is_prime = number > 1 начинается с False для 0, 1 и отрицательных чисел, которые никогда не бывают простыми.
  2. while divisor * divisor <= number and is_prime: останавливается на квадратном корне или сразу, как только найден делитель.
  3. number % divisor == 0 означает, что divisor делит число нацело.
  4. Для 29 цикл пробует только 2, 3, 4 и 5, после чего может сказать, что число простое.

Когда это нужно?

  • Числовые головоломки и упражнения, например вывод простых чисел или разложение на простые множители.
  • Понимание того, почему досрочная остановка и проверка только до предела ускоряют циклы.
  • Проверка ввода в математических инструментах.

Когда это не нужно

  • Все простые до большого предела: решето Эратосфена гораздо быстрее проверки каждого числа.
  • Криптография с числами из сотен цифр: настоящие системы используют вероятностные тесты.

Пример кода

Запустить код →
main.py
number = 29
is_prime = number > 1

divisor = 2
while divisor * divisor <= number and is_prime:
    if number % divisor == 0:
        is_prime = False
    divisor += 1

print(f"{number} is prime: {is_prime}")
Получить кнопку запуска для этого примера

Результат выполнения

29 is prime: True

Разбор кода

Циклу достаточно проверять делители, пока divisor * divisor <= number. Если у n есть делитель больше квадратного корня, он обязательно образует пару с меньшим делителем, который цикл уже проверил. Так сложность снижается до O(√n), а результат показывает, что 29 простое число.

Измените значения и запустите программу в онлайн-компиляторе Python CodeUtility без локальной установки Python.

Упражнения для практики

Попробуйте изменить код по подсказкам ниже. Если менять код и смотреть на результат, урок запомнится гораздо лучше, чем при простом чтении.

  1. Измените входные данные и предскажите результат до запуска.
  2. Добавьте проверку пустых или неверных данных.
  3. Вынесите обработку в отдельную функцию и проверьте её на нескольких наборах данных.
Запустить в компиляторе Python →

Частые ошибки

1 считается простым

У 1 только один делитель, поэтому оно не простое. Сначала проверьте number > 1.

Ошибка
is_prime = True  # 1 would be reported as prime
Исправление
is_prime = number > 1

Цикл до самого числа

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

Ошибка
for divisor in range(2, number):
Исправление
while divisor * divisor <= number:

Закончили этот урок?

Отметьте его как изученный, чтобы следить за прогрессом.

Далее: Разворот строки в Python →

Попрактикуйтесь на задаче

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

Все задачи