Проверка простоты до sqrt(n)
Эффективно проверяйте одно число
«Проверка простоты до sqrt(n)» — бесплатный урок Competitive Programming Academy на CoddyKit. Это урок 2 из 4. Ты можешь прочитать весь урок бесплатно ниже — а потом практиковать его прямо в браузере с встроенным редактором кода и ИИ-репетитором 24/7. Это часть пути обучения Competitive Programming Academy, и твой прогресс синхронизируется между веб-версией и приложением CoddyKit. Курс Competitive Programming Academy содержит 4 уроков всего.
Задача о простых числах
Один из основных математических навыков — определить, является ли отдельное число простым. Простое число имеет ровно два делителя: единицу и само себя. Давайте быстро это проверим. 🔍
Наивная проверка
Можно попробовать делить n на каждое число от 2 до n минус 1. Это правильно, но мучительно медленно, когда n велико.
Приём с квадратным корнем
Вот ключевая идея: достаточно проверять делители до квадратного корня из n. За этой границей новый множитель появиться не может.
Почему достаточно квадратного корня
Делители образуют пары, произведение которых равно n. Если бы оба делителя были больше квадратного корня, их произведение превысило бы n, что невозможно.
Граница цикла
Перебирайте i от 2, пока произведение i на i не превышает n. Использование i*i позволяет избежать ошибок вычислений с плавающей точкой, которые может вызвать квадратный корень для больших целых чисел.
while i * i <= n:
...Обработайте малые случаи
Числа меньше 2 никогда не бывают простыми, поэтому сразу отклоняйте их. Эта проверка делает основной цикл ясным и корректным.
if n < 2:
return FalseПолная функция
Объедините всё: проверьте малые значения, затем переберите возможные делители до квадратного корня. Если деление выполнено без остатка, n является составным.
def is_prime(n):
if n < 2:
return False
i = 2
while i * i <= n:
if n % i == 0:
return False
i += 1
return TrueУскорьте проверку
Проверьте 2 отдельно, а затем проверяйте только нечётные числа. Пропуск чётных примерно вдвое сокращает объём работы без дополнительной сложности.
if n % 2 == 0:
return n == 2Временная сложность
Эта проверка выполняется за время O(sqrt n). Для одного числа до миллиарда это всего около 30 000 простых операций.
Одно число, а не множество
Проверка с квадратным корнем особенно удобна для одного или нескольких запросов. Если простоту нужно проверять для целого диапазона, решето будет гораздо быстрее.
Избегайте ошибки с квадратным корнем
Сравнение с помощью i*i вместо math.sqrt позволяет избежать ошибок округления, из-за которых пограничные числа могут быть ошибочно признаны простыми или составными.
Быстрая проверка
Вспомните границу, благодаря которой эта проверка выполняется быстро.
Итоги
Теперь вы умеете проверять простоту одного числа за время O(sqrt n), обрабатывать малые значения, пропускать чётные числа и использовать i*i для точного результата. ✅
Часто задаваемые вопросы
Урок «Проверка простоты до sqrt(n)» бесплатный?
Да — полный текст урока «Проверка простоты до sqrt(n)» бесплатно доступен здесь в веб-версии. Чтобы практиковать его интерактивно (встроенный редактор кода и ИИ-репетитор 24/7) и разблокировать остальной курс Competitive Programming Academy, подпишись на CoddyKit PRO. Курс Competitive Programming Academy содержит 4 уроков всего.
Чему я научусь в уроке «Проверка простоты до sqrt(n)»?
Эффективно проверяйте одно число Ты практикуешь Competitive Programming Academy с помощью реального кода, который запускаешь прямо в браузере, и ИИ-репетитор 24/7 отвечает на твои вопросы во время урока.
Нужен ли мне опыт, чтобы начать Competitive Programming Academy?
Предыдущий опыт не требуется. Competitive Programming Academy на CoddyKit структурирован для всех уровней — от новичков до продвинутых, поэтому ты можешь начать отсюда или с самого начала и учиться в своем темпе. Это урок 2 из 4.
Сколько времени занимает урок «Проверка простоты до sqrt(n)»?
Большинство уроков CoddyKit занимают около 5–10 минут. Каждый из них компактный и интерактивный, поэтому ты постоянно делаешь прогресс и продолжаешь с того же места в веб-версии и приложении.
Можно ли писать и запускать код в этом уроке Competitive Programming Academy?
Да. Каждый урок Competitive Programming Academy включает встроенный редактор кода, поэтому ты пишешь и запускаешь реальный код прямо в браузере и получаешь моментальную обратную связь от AI — локальная установка не требуется.
Все уроки этого курса
- GCD, LCM и алгоритм Евклида
- Проверка простоты до sqrt(n)
- Решето Эратосфена
- Разложение на простые множители и делители