Проверка числа на простоту в Python
В этом уроке вы проверите, является ли число простым, перебирая делители только до его квадратного корня.
Введение
Какую задачу это решает
Простые числа стоят за шифрованием в интернете, хеш-таблицами и множеством головоломок. Проверка на простоту перебором всех делителей до самого числа работает для 29, но становится мучительно медленной для больших чисел. Одно небольшое наблюдение делает проверку гораздо быстрее.
Пример из жизни
Поиск делителей похож на попытку выложить плитку сплошным прямоугольником. 36 плиток укладываются как 1×36, 2×18, 3×12, 4×9 и 6×6. После квадрата (6×6) те же прямоугольники повторяются, только повёрнутые, поэтому дальше квадратного корня искать нечего. 29 плиток укладываются только как 1×29, значит, 29 простое.
number > 1🚪 Простыми могут быть только числа больше 1divisor * divisor <= number🪞 Остановиться на квадрате: дальше одни повторыnumber % divisor == 0🔍 Сплошной прямоугольник получился: число не простоеdivisor += 1➡️ Попробовать следующую ширинуПростое число - целое число больше 1, у которого только два положительных делителя: 1 и оно само.
Главное
is_prime = number > 1начинается с False для 0, 1 и отрицательных чисел, которые никогда не бывают простыми.while divisor * divisor <= number and is_prime:останавливается на квадратном корне или сразу, как только найден делитель.number % divisor == 0означает, чтоdivisorделит число нацело.- Для 29 цикл пробует только 2, 3, 4 и 5, после чего может сказать, что число простое.
Когда это нужно?
- Числовые головоломки и упражнения, например вывод простых чисел или разложение на простые множители.
- Понимание того, почему досрочная остановка и проверка только до предела ускоряют циклы.
- Проверка ввода в математических инструментах.
Когда это не нужно
- Все простые до большого предела: решето Эратосфена гораздо быстрее проверки каждого числа.
- Криптография с числами из сотен цифр: настоящие системы используют вероятностные тесты.
Пример кода
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 считается простым
У 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:
Закончили этот урок?
Отметьте его как изученный, чтобы следить за прогрессом.
Попрактикуйтесь на задаче
Примените материал этого урока к реальной задаче. Каждая задача запускается в браузере, с мгновенными тестами и разбором от ИИ.
- Проверка на простое число Определите, является ли число простым. Легко
- Наибольший простой делитель Найдите наибольший простой делитель положительного целого числа. Средне
- List Primes With a Sieve Find primes up to a limit by marking composite multiples. Средне