Workshop Hub
учебные материалы

Рассматриваем задачу: решето Эратосфена

8 ноября 2026 г. · 2 мин · python, algorithms, math

Предлагаю решить задачу вместе: без спешки, с объяснением каждой строки.

Задача

Найти все простые числа, не превосходящие n. Наивный перебор делителей слишком медленен — есть классический алгоритм-решето.

Решение


def primes_up_to(n: int) -> list[int]:
    sieve = [True] * (n + 1)
    sieve[0] = sieve[1] = False
    for p in range(2, int(n ** 0.5) + 1):
        if sieve[p]:
            for multiple in range(p * p, n + 1, p):
                sieve[multiple] = False
    return [i for i, is_prime in enumerate(sieve) if is_prime]


print(primes_up_to(30))

Как это работает

Список-решето помечает составные числа. Для каждого простого p вычёркиваются его кратные, начиная с p * p — меньшие кратные уже обработаны ранее.

Пример работы


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

Сложность

O(n log log n) по времени, O(n) по памяти.

Такой пример хорошо закрепляется практикой — перепишите решение руками и прогоните на своих тестах.

Related:

Читайте также