Ускорение процесса решето Эратосфена

1. Быстро вспомним алгоритм

Классическая реализация:

def eratosthenes(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = is_prime[1] = False

    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

    return is_prime

Время — O(N log log N). Нас будет интересовать не асимптотика, а то, насколько можно ускорить чисто реализацией.

2. Оптимизация №1 — не трогаем чётные числа

Идея простая:

* все чётные, кроме 2, составные
* если работаем только с нечётными, уменьшаем массив и количество итераций примерно вдвое

Реализация:

def eratosthenes_odd(n):
    if n < 2:
        return []

    size = (n + 1) // 2
    is_prime = [True] * size
    is_prime[0] = False

    limit = int(n ** 0.5) // 2
    for i in range(1, limit + 1):
        if is_prime[i]:
            p = 2 * i + 1
            start = (p * p) // 2
            for j in range(start, size, p):
                is_prime[j] = False

    return is_prime

3. Оптимизация №2 — вместо list[bool] использовать bytearray

Мысль:

* bool в Python — это объект
* bytearray — плотно упакованный буфер
* меньше накладных расходов и лучше ложится в CPU cache

Пример:

def eratosthenes_bytearray(n):
    is_prime = bytearray(b"\x01") * (n + 1)
    is_prime[0:2] = b"\x00\x00"

    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] = 0

    return is_prime

4. Оптимизация №3 — гибрид двух подходов

def eratosthenes_fast(n):
    if n < 2:
        return []

    size = (n + 1) // 2
    is_prime = bytearray(b"\x01") * size
    is_prime[0] = 0

    limit = int(n ** 0.5) // 2
    for i in range(1, limit + 1):
        if is_prime[i]:
            p = 2 * i + 1
            start = (p * p) // 2
            is_prime[start::p] = b"\x00" * (((size - start - 1) // p) + 1)

    return is_prime

5. Сравнение по времени

Тест на входе n = 10_000_000:

>>> eratosthenes.py
real  0.634s

>>> eratosthenes_odd.py
real  0.245s

>>> eratosthenes_bytearray.py
real  0.801s

>>> eratosthenes_fast.py
real  0.028s

Выводы:

* пропуск чётных (№1) даёт ~2.6× ускорение
* bytearray (№2) сам по себе не ускоряет — это больше про память
* гибрид (№3) даёт ~22.6× ускорение

Ключевой приём в №3:

is_prime[start::p] = b"\x00" * (((size - start - 1) // p) + 1)

Здесь нет Python-цикла — всё делает C-уровневая операция над слайсом. На таких задачах это огромная разница.

Общая мысль: в Python чаще всего ускоряют не асимптотику, а модель памяти и количество проходов по данным. Циклы + память → главные факторы.

👉 @PythonPortal