Решето Эратосфена
Находите все простые числа до N почти за линейное время
«Решето Эратосфена» — бесплатный урок Competitive Programming Academy на CoddyKit. Это урок 3 из 4. Ты можешь прочитать весь урок бесплатно ниже — а потом практиковать его прямо в браузере с встроенным редактором кода и ИИ-репетитором 24/7. Это часть пути обучения Competitive Programming Academy, и твой прогресс синхронизируется между веб-версией и приложением CoddyKit. Курс Competitive Programming Academy содержит 4 уроков всего.
Простые числа в большом количестве
Иногда нужны все простые числа до N, а не только результат одной проверки. Решето Эратосфена находит их все за один проход. 🧹
Главная идея
Сначала считайте каждое число простым. Затем вычёркивайте кратные каждого найденного простого числа, оставляя только настоящие простые числа.
Настройте флаги
Создайте логический список, в котором индекс i показывает, является ли i простым. Этот массив служит основой, на которой работает решето.
is_prime = [True] * (n + 1)
is_prime[0] = is_prime[1] = FalseПереберите кандидатов
Последовательно увеличивайте i. Когда вы впервые достигаете числа, для которого всё ещё установлен флаг True, это новое простое число, у которого нет меньшего делителя.
Вычеркните кратные
Для каждого простого i помечайте 2i, 3i, 4i и так далее как непростые. У этих кратных явно есть делитель i.
for j in range(i * i, n + 1, i):
is_prime[j] = FalseНачинайте с квадрата i
Начинайте вычёркивание с i*i, а не с 2i. Каждое меньшее кратное уже удалено предыдущим простым числом, поэтому его можно пропустить.
Остановитесь у квадратного корня
Достаточно выполнять решето, пока i*i не превышает N. После квадратного корня каждый оставшийся флаг True уже соответствует простому числу.
Полное решето
Объедините внешний перебор и внутреннее вычёркивание. После цикла каждый индекс с флагом True соответствует подтверждённому простому числу.
for i in range(2, int(n ** 0.5) + 1):
if is_prime[i]:
for j in range(i * i, n + 1, i):
is_prime[j] = FalseСоберите простые числа
Считайте завершённые флаги в список с помощью включения. Теперь у вас есть все простые числа до N, готовые для быстрых запросов.
primes = [i for i, p in enumerate(is_prime) if p]Почему это быстро
Решето работает примерно за O(n log log n), то есть почти за линейное время. Поэтому оно намного эффективнее повторяющихся проверок отдельных чисел.
Помните о памяти
Массив флагов использует объём памяти, пропорциональный N. Для очень больших ограничений оцените доступную память перед выделением массива.
Быстрая проверка
Вспомните небольшую оптимизацию во внутреннем цикле.
Итоги
Теперь вы умеете строить решето, чтобы перечислить все простые числа до N почти за линейное время: начинать обработку каждого простого числа с i*i и останавливаться у квадратного корня. ✅
Часто задаваемые вопросы
Урок «Решето Эратосфена» бесплатный?
Да — полный текст урока «Решето Эратосфена» бесплатно доступен здесь в веб-версии. Чтобы практиковать его интерактивно (встроенный редактор кода и ИИ-репетитор 24/7) и разблокировать остальной курс Competitive Programming Academy, подпишись на CoddyKit PRO. Курс Competitive Programming Academy содержит 4 уроков всего.
Чему я научусь в уроке «Решето Эратосфена»?
Находите все простые числа до N почти за линейное время Ты практикуешь Competitive Programming Academy с помощью реального кода, который запускаешь прямо в браузере, и ИИ-репетитор 24/7 отвечает на твои вопросы во время урока.
Нужен ли мне опыт, чтобы начать Competitive Programming Academy?
Предыдущий опыт не требуется. Competitive Programming Academy на CoddyKit структурирован для всех уровней — от новичков до продвинутых, поэтому ты можешь начать отсюда или с самого начала и учиться в своем темпе. Это урок 3 из 4.
Сколько времени занимает урок «Решето Эратосфена»?
Большинство уроков CoddyKit занимают около 5–10 минут. Каждый из них компактный и интерактивный, поэтому ты постоянно делаешь прогресс и продолжаешь с того же места в веб-версии и приложении.
Можно ли писать и запускать код в этом уроке Competitive Programming Academy?
Да. Каждый урок Competitive Programming Academy включает встроенный редактор кода, поэтому ты пишешь и запускаешь реальный код прямо в браузере и получаешь моментальную обратную связь от AI — локальная установка не требуется.
Все уроки этого курса
- GCD, LCM и алгоритм Евклида
- Проверка простоты до sqrt(n)
- Решето Эратосфена
- Разложение на простые множители и делители