Временная сложность
Лучший: O(n log log n)
Средний: O(n log log n)
Худший: O(n log log n)
Решето Эратосфена — это классический алгоритм для нахождения всех простых чисел до заданного предела n. Он работает путём последовательного вычёркивания кратных каждого простого числа, начиная с 2.
Как работает алгоритм:
1. Создать булев массив, в котором числа от 2 до n изначально отмечены как потенциально простые
2. Для каждого i от 2 до √n, если i всё ещё отмечено как простое, отметить все его кратные (начиная с i²) как составные
3. Числа, оставшиеся отмеченными после завершения цикла, являются простыми числами ≤ n
Почему вычёркивание начинается с i²?
Все меньшие кратные числа i (2i, 3i, …, (i−1)i) уже были вычеркнуты меньшими простыми числами.
Временная сложность:
Лучший случай: O(n log log n)
Средний случай: O(n log log n)
Худший случай: O(n log log n)
Пространственная сложность: O(n)
Свойства:
- Детерминированный алгоритм, не использующий случайность
- Эффективно использует кэш, если n помещается в оперативную память
- Фундаментальный алгоритм для теории чисел и предварительной обработки данных в криптографии
Алгоритм назван в честь древнегреческого математика Эратосфена Киренского (~276–194 гг. до н. э.). Это решето остаётся одним из наиболее эффективных способов нахождения всех небольших простых чисел и служит основой для многих этапов предварительной обработки при факторизации.
Похожие алгоритмы
Частые вопросы
- Что такое Решето Эратосфена?
- Решето Эратосфена — это классический алгоритм для нахождения всех простых чисел до заданного предела n. Он работает путём последовательного вычёркивания кратных каждого простого числа, начиная с 2.
- Какова сложность Решето Эратосфена?
- Время (среднее): O(n log log n) · Память: O(n)
- Для кого предназначена визуализация Решето Эратосфена?
- Визуализация Решето Эратосфена рассчитана на средний уровень в категории «Математика». Полезна для студентов, подготовки к собеседованиям и практического изучения.
- Какие алгоритмы связаны с Решето Эратосфена?
- В той же категории (Математика) вы можете изучить: Euclidean Algorithm. Каждый из них имеет интерактивную визуализацию.