Решето Эратосфена на Python: как работает алгоритм и как его ускорить

Решето Эратосфена находит все простые числа от 2 до n. Выпишите числа подряд, возьмите первое незачёркнутое и вычеркните все кратные ему, затем повторите со следующим незачёркнутым. Когда квадрат очередного числа станет больше n, остановитесь: всё, что не зачёркнуто, и есть простые числа.

На Python алгоритм умещается в десяток строк со списком из True и False. Если заменить список на bytearray или массив NumPy, тот же код на десяти миллионах чисел работает в 4–35 раз быстрее. Ниже разберём решето на числах до 30, напишем функцию, ускорим её и покажем, когда решето не нужно совсем. Если синтаксис def пока непривычен, сначала загляните в разбор функций в Python.

CheckroiПодборка курсов по Python568 курсов • 51 школаСравните цены, школы, программу и найдите выгодные предложения по обучениюСравнить→

Как работает решето Эратосфена

Алгоритм назван по имени древнегреческого математика Эратосфена Киренского. Описание метода, как указано в статье Википедии о решете, сохранилось во «Введении в арифметику» Никомаха Герасского.

Пройдём алгоритм руками на числах от 2 до 30:

1. Выписываем все числа от 2 до 30.
2. Первое число 2 простое. Вычёркиваем каждое второе после него: 4, 6, 8 и так до 30.
3. Следующее незачёркнутое число 3. Вычёркиваем кратные трём, начиная с 9: из новых уходят 9, 15, 21 и 27, остальные уже убрала двойка.
4. Следующее незачёркнутое число 5. Начинаем с 25 и вычёркиваем 25, число 30 уже зачёркнуто.
5. Следующее незачёркнутое число 7, но 7 × 7 = 49 больше 30. Останавливаемся.

Незачёркнутыми остались 10 чисел: 2, 3, 5, 7, 11, 13, 17, 19, 23 и 29. Это все простые числа до 30.

Почему начинаем с квадрата и останавливаемся на корне

Все кратные числа p, которые меньше p², уже вычеркнуты раньше. Например, 3 × 5 = 15 убрала тройка, когда до пятёрки дело ещё не дошло. Поэтому начинать с 2p бессмысленно: каждое такое число проверялось бы второй раз.

С остановкой похожая логика. У любого составного числа до n есть делитель не больше √n, значит, после этой границы вычёркивать уже нечего. В Википедии оба правила записаны так: числа «можно зачеркивать, начиная сразу с числа p²», а «останавливать алгоритм можно, когда p² станет больше, чем n».

Решето Эратосфена на Python: базовый код

Заводим список Python из флагов длиной n + 1, чтобы индекс совпадал с самим числом. Флаг True значит «пока не зачёркнуто».

def sieve(n):
    if n < 2:
        return []
    is_prime = [True] * (n + 1)
    is_prime[0] = is_prime[1] = False
    p = 2
    while p * p <= n:
        if is_prime[p]:
            for multiple in range(p * p, n + 1, p):
                is_prime[multiple] = False
        p += 1
    return [i for i in range(n + 1) if is_prime[i]]

print(sieve(50))
print(len(sieve(1_000_000)))

Вывод:

[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]
78498

Что здесь происходит:

• Проверка n < 2 нужна не для красоты. Без неё вызов sieve(0) падает с IndexError: в списке из одного элемента нет индекса 1.
• Внешний цикл while идёт, пока p * p <= n. Это та же остановка на корне, только без извлечения корня.
• Внутренний range(p * p, n + 1, p) шагает по кратным p начиная с квадрата. Третий аргумент range задаёт шаг, и точно так же шаг работает в срезах Python: этим воспользуемся в быстрой версии.
• В конце списковое включение собирает индексы, где флаг остался True.

Число 78 498 легко проверить: столько простых чисел меньше миллиона, это значение есть в последовательности A006880 энциклопедии OEIS.

Как ускорить решето на Python

Базовая версия тратит время на внутренний цикл, который Python выполняет по одному элементу, и на память. Список из десяти миллионов флагов занимает 80 МБ, потому что каждый элемент хранится как ссылка на объект. Ниже три приёма, от простого к сильному.

Срезы и bytearray вместо цикла

Внутренний цикл можно заменить одним присваиванием среза: все кратные p обнуляются за одну операцию на уровне C. А bytearray хранит каждый флаг в одном байте: на десяти миллионах чисел это 10 МБ вместо 80.

from math import isqrt

def sieve_fast(n):
    if n < 2:
        return []
    is_prime = bytearray([1]) * (n + 1)
    is_prime[0] = is_prime[1] = 0
    for p in range(2, isqrt(n) + 1):
        if is_prime[p]:
            is_prime[p * p::p] = bytes(len(range(p * p, n + 1, p)))
    return [i for i, flag in enumerate(is_prime) if flag]

print(sieve_fast(30))
print(len(sieve_fast(10_000_000)))

[2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
664579

Справа от знака равенства стоит строка нулевых байтов ровно той длины, что у среза. Если длина не совпадёт, Python выдаст ошибку, поэтому её считает len(range(...)). Граница цикла берётся через isqrt: по документации Python функция возвращает целую часть точного квадратного корня. С версии 3.15 она живёт в модуле math.integer, но и from math import isqrt по-прежнему работает.

Только нечётные числа

Из чётных чисел простое только 2, поэтому хранить остальные чётные незачем. Пусть ячейка с номером i отвечает за число 2i + 1: памяти нужно вдвое меньше, и вычёркивать приходится вдвое реже.

from math import isqrt

def sieve_odd(n):
    if n < 2:
        return []
    size = (n - 1) // 2          # ячейка i хранит число 2*i + 1
    is_prime = bytearray([1]) * (size + 1)
    is_prime[0] = 0              # 1 не простое
    for i in range(1, (isqrt(n) - 1) // 2 + 1):
        if is_prime[i]:
            p = 2 * i + 1
            start = p * p // 2
            is_prime[start::p] = bytes(len(range(start, size + 1, p)))
    return [2] + [2 * i + 1 for i, flag in enumerate(is_prime) if flag]

print(sieve_odd(30))
print(len(sieve_odd(10_000_000)))

[2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
664579

Индекс квадрата считается как p * p // 2: квадрат нечётного числа нечётный, и целочисленное деление сразу даёт его номер ячейки. Шаг p по ячейкам означает шаг 2p по числам, так чётные кратные пропускаются сами. Если знаки // и % путаются, откройте разбор операторов Python.

NumPy

Массив NumPy делает то же, что bytearray, но ещё и собирает ответ без цикла на Python. Библиотеку ставят командой pip install numpy, удобнее всего внутри виртуального окружения.

import numpy as np

def sieve_numpy(n):
    is_prime = np.ones(n + 1, dtype=bool)
    is_prime[:2] = False
    for p in range(2, int(n ** 0.5) + 1):
        if is_prime[p]:
            is_prime[p * p::p] = False
    return np.flatnonzero(is_prime)

primes = sieve_numpy(100)
print(primes)
print(len(sieve_numpy(10_000_000)))

[ 2  3  5  7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89
 97]
664579

Функция np.flatnonzero возвращает индексы ненулевых элементов, это сказано в её описании в документации NumPy. Индексы и есть простые числа. Здесь границу можно считать через int(n ** 0.5): на числах до десятков миллионов дробный корень ещё точен. Где он начинает врать, показано в разделе об ошибках.

Сколько выигрывает каждый способ

Мы прогнали все четыре функции на n = 10 000 000 и взяли лучшее время из трёх запусков timeit. Окружение: Python 3.14.7, NumPy 2.4.4, процессор Apple M4 Pro. На другом компьютере секунды будут другими, а порядок останется тем же.

Для учебной задачи хватит базовой версии, её проще всего объяснить преподавателю. Я бы брал NumPy, если он уже стоит в проекте, а вариант с нечётными числами оставил для олимпиад и окружений, где сторонние библиотеки ставить нельзя.

Когда решето не нужно

Решето хорошо, когда нужны все простые числа подряд. Если вопрос звучит как «простое ли число 91?», строить таблицу на сотню элементов ради одного ответа незачем. Хватит перебора делителей до корня:

from math import isqrt

def is_prime(n):
    if n < 2:
        return False
    if n % 2 == 0:
        return n == 2
    for d in range(3, isqrt(n) + 1, 2):
        if n % d == 0:
            return False
    return True

print(is_prime(97), is_prime(91), is_prime(2), is_prime(1))
print([n for n in range(90, 110) if is_prime(n)])

True False True False
[97, 101, 103, 107, 109]

Число 91 выглядит простым, но равно 7 × 13, на этом часто ловятся в задачах. Проверку делимости здесь делает оператор остатка, подробно он разобран в статье про остаток от деления в Python.

Граница между подходами проходит по количеству чисел. Проверить is_prime каждое число до миллиона заняло у нас 0,599 с, а базовое решето на том же диапазоне справилось за 0,028 с, то есть примерно в 21 раз быстрее.

Сложность алгоритма

Решето Эратосфена выполняет O(n log log n) операций, такую оценку приводит Википедия. Множитель log log n растёт так медленно, что на практике время почти пропорционально n: если чисел в десять раз больше, ждать придётся примерно в десять раз дольше.

Узкое место чаще не время, а память. Флагов столько же, сколько чисел, поэтому решето до миллиарда в виде списка Python потребует около 8 ГБ. В таких задачах помогают bytearray, хранение только нечётных или сегментированное решето.

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

• Потерялось последнее число. Список заведён как [True] * n, а цикл идёт по range(2, n). Тогда n в проверку не попадает: такая функция для n = 13 вернёт [2, 3, 5, 7, 11] без самой тринадцати.
  Решение: длина списка n + 1 и range(..., n + 1).
• Ноль и единица в ответе. Флаги для 0 и 1 забыли выставить в False, и они попали в список простых.
  Решение: is_prime[0] = is_prime[1] = False сразу после создания списка.
• Падение на маленьких n. Для n = 0 строка is_prime[1] = False вызывает IndexError.
  Решение: в начале функции if n < 2: return [].
• Неточный корень на больших числах. int(n ** 0.5) считает через дробные числа. Для 10**30 - 1 он даёт 1 000 000 000 000 000, хотя верный ответ 999 999 999 999 999.
  Решение: isqrt(n), она считает в целых числах типа int без округления.
• Вычёркивание с 2p. Ошибкой это не назовёшь, ответ будет верным. Но вы зря проходите числа, которые уже зачёркнуты.
  Решение: начинайте с p * p.

Если хочется закрепить тему на практике, в подборке задач по Python для начинающих есть упражнения, где простые числа пригодятся.

Канал основателя Checkroi Вани БуявцаЗабирайте промпты и обучение по нейросетям в моём Телеграм-каналеБольше 3 700 человек уже применяют Claude Code, ChatGPT и другие нейросети в работе, учёбе, бизнесе и жизниПерейти в канал→

Где освоить Python системно

На решете хорошо видно, как одна замена структуры данных ускоряет код в несколько раз. Если хотите разбираться в алгоритмах и структурах данных по программе с проверкой домашних задач, сравните курсы Python: у каждого в каталоге есть цена, длительность и отзывы выпускников.

Курс	Школа	Стоимость со скидкой	В рассрочку	Длитель­ность	Обзор курса от Checkroi
Профессия «Python-разработчик» Перейти на сайт курса	Skillbox	157 335 ₽	5987 ₽/мес.	10 месяцев	Обзор курса
Fullstack-разработчик на Python Перейти на сайт курса	Нетология	137 000 ₽	7125 ₽/мес.	21 месяц	Обзор курса
ДО Профессия Python-разработчик Перейти на сайт курса	GeekBrains	149 001 ₽	3167 ₽/мес.	10 месяцев	Обзор курса
Автоматизированное тестирование на Python Перейти на сайт курса	Skillbox	122 226 ₽	4108 ₽/мес.	9 месяцев	Обзор курса
Профессия Python-разработчик Перейти на сайт курса	SkillFactory	140 040 ₽	4279 ₽/мес.	10 месяцев	Обзор курса

• 

  Профессия «Python-разработчик»

  Skillbox157 335 ₽5987 ₽/мес10 месяцев
  Перейти на сайт курсаОбзор
• 

  Fullstack-разработчик на Python

  Нетология137 000 ₽7125 ₽/мес21 месяц
  Перейти на сайт курсаОбзор
• 

  ДО Профессия Python-разработчик

  GeekBrains149 001 ₽3167 ₽/мес10 месяцев
  Перейти на сайт курсаОбзор
• 

  Автоматизированное тестирование на Python

  Skillbox122 226 ₽4108 ₽/мес9 месяцев
  Перейти на сайт курсаОбзор
• 

  Профессия Python-разработчик

  SkillFactory140 040 ₽4279 ₽/мес10 месяцев
  Перейти на сайт курсаОбзор

Больше программ — в полном каталоге курсов по Python