Решето Эратосфена: просеиваем простые числа | OTUS
⚡ Подписка на курсы OTUS!
Интенсивная прокачка навыков для IT-специалистов!
Подробнее

Курсы

Программирование
Python Developer. Professional
-3%
Разработчик на Spring Framework
-5%
iOS Developer. Professional
-8%
Golang Developer. Professional
-6%
Базы данных
-12%
Agile Project Manager
-5%
Android Developer. Professional
-11%
Microservice Architecture
-5%
C++ Developer. Professional
-5%
Highload Architect
-6%
JavaScript Developer. Basic
-8%
Backend-разработчик на PHP
-9%
Архитектура и шаблоны проектирования C# Developer. Professional
-9%
Team Lead
-6%
Kotlin Backend Developer
-9%
Разработчик программных роботов (RPA) на базе UiPath и PIX Unity Game Developer. Basic Разработчик голосовых ассистентов и чат-ботов Node.js Developer Интенсив «Оптимизация в Java» Супер - интенсив по паттернам проектирования Супер - интенсив по Kubernetes iOS Developer. Basic Супер-интенсив «СУБД в высоконагруженных системах» Супер-интенсив "Tarantool"
Инфраструктура
DevOps практики и инструменты
-12%
Базы данных
-12%
Network engineer. Basic
-10%
Network engineer
-4%
Инфраструктурная платформа на основе Kubernetes
-6%
Экспресс-курс по управлению миграциями (DBVC)
-10%
Мониторинг и логирование: Zabbix, Prometheus, ELK
-10%
Administrator Linux. Professional
-6%
Разработчик IoT
-13%
Основы Windows Server Cloud Solution Architecture Разработчик голосовых ассистентов и чат-ботов VOIP инженер Супер-практикум по работе с протоколом BGP NoSQL Супер-практикум по использованию и настройке GIT Супер-интенсив «СУБД в высоконагруженных системах» Экспресс-курс «IaC Ansible»
Специализации Курсы в разработке Подготовительные курсы
+7 499 938-92-02

Решето Эратосфена: просеиваем простые числа

Algo_deep_1.04_Site-5020-5f8450.png

Что такое решето Эратосфена, знает сегодня, пожалуй, любой школьник, интересующийся математикой. Но не всякий знает, какова алгоритмическая сложность этого «просеивателя».

Напомним условие задачи

Необходимо найти все простые числа, меньшие или равные заданному числу N.

Запишем в ряд все числа от 1 до N и будем вычёркивать оттуда все числа, кратные двойке, но больше двойки, затем, все числа, кратные тройке, но больше тройки и т. д.

Если число уже вычеркнуто, пропускаем его и переходим к следующему. Так мы продолжаем, пока не дойдем до N. В итоге у нас останутся невычеркнутыми только простые числа.

Почему так?

Потому что оставшиеся числа не делятся ни на что, кроме самих себя и единицы. Это легко доказать методом от противного. Допустим, осталось число n и оно делится на некоторое k, такое, что 1 < k < n. Значит, оно должно было быть вычеркнуто, когда вычёркивали числа, делящиеся на k. А оно у нас не вычеркнулось.

Оптимизации

Можно просеивать только нечётные числа, ибо чётные — заведомо составные. Можно просеивать только числа до √N.

Теперь оценим потребление памяти и вычислительную сложность этого алгоритма

По памяти этот алгоритм требует O(N), потому что размер целевого массива N и никакой дополнительной памяти не используется.

Оценим теперь его вычислительную сложность (интересно, что оптимизации на асимптотическую сложность не влияют, а уменьшают только коэффициент). Для каждого простого p вычёркиваем числа N / p раз. Общее число действий, которые мы производим, равно сумме: 1-20219-3fb712.jpg Примем как данность, что число простых чисел, меньших либо равных N, приблизительно равно N / ln N, следовательно, k-e простое число приблизительно равно k ln k.

Оценим сумму: 2-20219-d0246d.jpg

Оценим новую сумму как интеграл: 3-20219-00449e.jpg

Интересно, знал ли об этом Эратосфен?

Не пропустите новые полезные статьи!

Спасибо за подписку!

Мы отправили вам письмо для подтверждения вашего email.
С уважением, OTUS!

Автор
0 комментариев
Для комментирования необходимо авторизоваться