Чтобы проверить число на простоту в Python, переберите делители от 2 до квадратного корня из n: если ни один не делит число нацело — оно простое. Для одиночной проверки это даёт сложность O(√n). Для очень больших чисел применяйте sympy.isprime(), а для списка всех простых до N — решето Эратосфена со сложностью O(n log log n).
Ниже — четыре рабочих метода с готовым кодом, честным сравнением по скорости и таблицей «метод → сложность → когда применять». Материал доведён до практического уровня: вы сможете выбрать алгоритм под свою задачу, а не просто скопировать первый попавшийся цикл.
Что такое простое число
Простое число — это натуральное число больше 1, которое делится без остатка только на 1 и на само себя. Например, 2, 3, 5, 7 и 11 — простые, а 4, 6, 8 и 9 — составные, потому что имеют дополнительные делители. Число 1 не считается простым по определению. Двойка — единственное чётное простое число; все остальные чётные числа делятся на 2 и потому составные. На этом наблюдении построены почти все оптимизации, которые мы разберём дальше.
- ПОКАЖЕМ, КАК РАЗВЕРНУТЬ МОДЕЛЬ нейросети DEEPSEEK R1 ПРЯМО НА СВОЁМ КОМПЬЮТЕРЕ
- Где и как применять? Потестируем модель после установки на разных задачах
- Как дообучить модель под себя?
Метод 1. Наивная проверка перебором — O(n)
Самый прямолинейный способ: перебрать все числа от 2 до n − 1 и проверить, делится ли на них n. Если найден хотя бы один делитель — число составное.
def is_prime_naive(n):
if n < 2:
return False
for i in range(2, n):
if n % i == 0:
return False
return True
print(is_prime_naive(17)) # True
print(is_prime_naive(18)) # False
Код корректен, но неэффективен: он делает до n − 2 итераций, поэтому его асимптотическая сложность — O(n). Для учебных примеров и небольших чисел этого достаточно, но уже на миллионах проверка ощутимо тормозит.
Метод 2. Оптимизация до √n — O(√n)
Ключевая идея: если у числа n есть делитель больше √n, то у него обязательно есть и парный делитель меньше √n. Значит, проверять делители выше квадратного корня бессмысленно — все составные числа «отсеются» раньше. Это сокращает число итераций с n до √n.
import math
def is_prime(n):
if n < 2:
return False
for i in range(2, math.isqrt(n) + 1):
if n % i == 0:
return False
return True
print(is_prime(97)) # True
print(is_prime(100)) # False
Здесь применена функция math.isqrt() — она возвращает целочисленный квадратный корень и, в отличие от math.sqrt(), не даёт ошибок округления с плавающей точкой на больших числах. Сложность метода — O(√n). Это разумный выбор по умолчанию для одиночной проверки чисел вплоть до порядка 10¹².
Метод 3. Проверка по формуле 6k ± 1 — быстрее в ~3 раза
Асимптотику O(√n) можно сохранить, но заметно сократить константу. Все простые числа больше 3 представимы в виде 6k − 1 или 6k + 1, потому что числа вида 6k, 6k ± 2 и 6k + 3 делятся на 2 или на 3. Значит, после отсева кратных двойке и тройке достаточно проверять делители с шагом 6.
def is_prime_fast(n):
if n <= 1:
return False
if n <= 3:
return True
if n % 2 == 0 or n % 3 == 0:
return False
i = 5
while i * i <= n:
if n % i == 0 or n % (i + 2) == 0:
return False
i += 6
return True
print(is_prime_fast(7919)) # True
Формально сложность та же — O(√n), — но на практике функция выполняет примерно втрое меньше делений, чем простой перебор до корня. Это лучший вариант «на чистом Python» без внешних библиотек.
- ПОКАЖЕМ, КАК РАЗВЕРНУТЬ МОДЕЛЬ нейросети DEEPSEEK R1 ПРЯМО НА СВОЁМ КОМПЬЮТЕРЕ
- Где и как применять? Потестируем модель после установки на разных задачах
- Как дообучить модель под себя?
Метод 4. Решето Эратосфена — O(n log log n) для списка простых
Когда нужна не одна проверка, а все простые числа до заданного предела N, поштучная проверка каждого числа неэффективна. Классическое решение — решето Эратосфена. Алгоритм создаёт массив булевых флагов и последовательно вычёркивает кратные каждого найденного простого, начиная с его квадрата.
import math
def sieve_of_eratosthenes(limit):
is_prime = [True] * (limit + 1)
is_prime[0] = is_prime[1] = False
for i in range(2, math.isqrt(limit) + 1):
if is_prime[i]:
for j in range(i * i, limit + 1, i):
is_prime[j] = False
return [i for i, prime in enumerate(is_prime) if prime]
print(sieve_of_eratosthenes(30))
# [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
Временная сложность решета — O(n log log n), что почти линейно. Плата за скорость — память: алгоритм хранит массив на n + 1 элемент, то есть требует O(n) памяти. Для генерации всех простых до нескольких миллионов это по-прежнему самый быстрый практичный подход. Подробнее об идее вычёркивания кратных — в описании алгоритма.
Метод 5. sympy.isprime() — для очень больших чисел
Если вы работаете с числами в десятки и сотни разрядов (например, в криптографии), перебор делителей нежизнеспособен даже при O(√n). Здесь применяют вероятностные тесты — Миллера–Рабина и Baillie–PSW. В Python их реализация уже готова в библиотеке SymPy.
from sympy import isprime
print(isprime(17)) # True
print(isprime(561)) # False — число Кармайкла, ловушка теста Ферма
print(isprime(2**89 - 1)) # True — работает с огромными числами мгновенно
Функция isprime() комбинирует пробное деление для малых делителей и детерминированный вариант теста Миллера–Рабина, поэтому корректно распознаёт даже числа Кармайкла, на которых спотыкается наивный тест Ферма. Детали реализации — в документации SymPy. Установка: pip install sympy.
Сравнение методов: что выбрать
Разные задачи требуют разных алгоритмов. Наивный перебор перестаёт быть пригодным примерно на n > 10⁶, версия до √n уверенно держит числа до 10¹², а для криптографических размеров нужен только sympy.isprime(). Если же цель — не проверить одно число, а получить их список, вне конкуренции решето Эратосфена.
→ Решето Эратосфена
→ sympy.isprime()
→ 6k ± 1 (is_prime_fast)
→ Перебор до √n
Таблица: метод → сложность → когда применять
| Метод | Время | Память | Когда применять |
|---|---|---|---|
| Наивный перебор | O(n) | O(1) | Учёба, малые числа (n < 1000) |
| Перебор до √n | O(√n) | O(1) | Одиночная проверка до ~10¹² |
| Формула 6k ± 1 | O(√n) | O(1) | Та же задача, но в ~3 раза быстрее |
| Решето Эратосфена | O(n log log n) | O(n) | Список всех простых до N |
| sympy.isprime() (Миллер–Рабин / BPSW) | ≈ O(k · log³n) | O(1) | Очень большие числа, криптография |
Проверка на простоту — частный случай работы с делителями. Если вам нужно не просто узнать факт простоты, а разложить число на множители, посмотрите разбор простой факторизации положительных чисел в Python. А для задач вроде сокращения дробей пригодится алгоритм вычисления наибольшего общего делителя. Понимание асимптотической сложности, которое мы использовали выше, лежит в основе всех структур данных — например, кучи (heap).
Часто задаваемые вопросы
Почему достаточно проверять делители только до √n?
Делители числа идут парами: если n = a × b и a ≤ b, то a не превышает √n. Найдя все делители до корня, вы автоматически покрываете и их «пары» выше корня. Поэтому проверка выше √n избыточна и лишь замедляет алгоритм.
Является ли число 1 простым?
Нет. По определению простое число должно быть больше 1 и иметь ровно два различных делителя — единицу и само себя. У числа 1 только один делитель, поэтому оно не простое и не составное.
Какой метод самый быстрый для одиночной проверки?
Для обычных целых чисел — вариант с формулой 6k ± 1: та же сложность O(√n), но примерно втрое меньше операций. Для чисел в десятки разрядов и больше — sympy.isprime(), использующий вероятностные тесты.
В чём разница между решетом Эратосфена и перебором делителей?
Перебор проверяет одно число за O(√n). Решето за один проход находит сразу все простые до предела N со сложностью O(n log log n), но требует O(n) памяти. Решето выгодно, когда нужно много простых чисел, а не одна проверка.
Можно ли сгенерировать нужный код автоматически?
Да, современные ИИ-ассистенты пишут подобные функции по текстовому запросу. Обзор инструментов — в материале об ИИ для написания кода Python онлайн.
Заключение
Проверка числа на простоту в Python — это не один алгоритм, а спектр решений под разные задачи. Для учебных примеров хватит перебора до √n, для продакшена на чистом Python выбирайте формулу 6k ± 1, для генерации списков — решето Эратосфена, а для больших чисел — sympy.isprime(). Ориентируйтесь на таблицу сложности выше: правильный выбор метода экономит и время выполнения, и память.
- Освой нейросеть Perplexity и узнай, как пользоваться функционалом остальных ИИ в одном
- УЧАСТВОВАТЬ ЗА 0 РУБ.
- Расскажем, как получить подписку
- ПОКАЖЕМ, КАК РАЗВЕРНУТЬ МОДЕЛЬ нейросеть DEEPSEEK R1 ПРЯМО НА СВОЁМ КОМПЬЮТЕРЕ
