DEV//UNIT
← Алгоритмыmath

Решето Эратосфена

Все простые до N: вычёркиваем кратные каждого простого.

время O(n log log n)память O(n)уровень: начальный
Что происходит сейчас0/0
Нажмите Play, чтобы запустить сценарий
TypeScript — активная строка подсвечена шагом
1function sieveOfEratosthenes(n: number): number[] {
2  const isPrime = new Array(n + 1).fill(true)
3  isPrime[0] = isPrime[1] = false
4 
5  for (let p = 2; p * p <= n; p++) {
6    if (!isPrime[p]) continue
7    for (let m = p * p; m <= n; m += p) {
8      isPrime[m] = false // кратно p — вычёркиваем
9    }
10  }
11 
12  return isPrime.map((ok, i) => (ok ? i : -1)).filter((i) => i > 0)
13}

Проблема

Все простые до N: вычёркиваем кратные каждого простого.

Что вы видите

Сетка чисел: 2 вычёркивает чётные, 3 — кратные тройки… невычеркнутые — простые.

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

Каждое составное число вычёркивается ровно один раз — своим наименьшим простым множителем. O(n log log n) — быстрее перебора делителей на порядки.

Пошаговый разбор

  1. 01

    Вычёркивание

    Кратные p, начиная с p².

  2. 02

    Переход

    Следующее невычеркнутое простое.

  3. 03

    Итог

    Невычеркнутые — простые.

Complexity и ограничения

time
O(n log log n)
space
O(n)

Сложность см. в шапке страницы.

Edge cases

  • Пустой вход

    Корректная тривиальная обработка.

  • Вырожденный случай

    Минимум работы — сразу ответ.

Где встречается в реальности

Криптография

Поиск больших простых для RSA.

Задачи

Проверки на простоту в олимпиадах.

Хеш-таблицы

Простые размеры таблиц для равномерности.

Связанные алгоритмы

Бинарный поискНОД (алгоритм Евклида)
Shorts

«Найти все простые быстрее, чем проверять каждое»

Тот же сценарий StepSequence в вертикальной композиции — с safe zones и записью WebM ниже на странице.

Shorts 9:16

Вертикальная композиция строится той же последовательностью шагов, что и страница: safe zones отмечены пунктиром (там живёт UI платформ), биты сценария подсвечиваются по прогрессу. Кнопка записи сохраняет WebM — детерминированная StepSequence даёт воспроизводимый ролик без монтажа.

Найти все простые быстрее, чем проверять каждое
Нажмите Play
Бит 1/6 · 0–2 с
Hook
script-setup.ru/algorithms/sieve