Где применяется
1. Задача
Простое число (prime) это число больше 1, которое делится только на 1 и на само себя: 2, 3, 5, 7, 11. Тебе нужны все простые числа до миллиона, и быстро.
Очевидный способ: проверять каждое число отдельно. Простое ли 91? Пробуешь делить его на 2, 3, 4 и дальше, вплоть до квадратного корня из 91 (это примерно 9,5). На 7 оно делится: 91 = 7 · 13, значит, не простое. Для одного числа это быстро. Но если повторить такую проверку для миллиона чисел, получится миллион отдельных поисков, и в них одни и те же деления повторяются снова и снова.
Есть способ найти все простые числа диапазона почти за один проход. Вместо того чтобы проверять каждого кандидата, вычёркивай числа, которые простыми быть не могут.
Этот шаг из платной части
Бесплатные шаги в начале курса (их 33) открыты всем: урок, задача и тесты. Этот шаг открывается с полным доступом. Начни с бесплатного аккаунта и бесплатных шагов.
Завести бесплатный аккаунтПосмотреть, что входитКак узнать
Эти слова в условии значат этот паттерн
- сократить дробь до несократимого вида
- перечислить все простые числа до n
- ответ по модулю 1e9+7
- когда снова совпадут два повторяющихся интервала (НОК)
Похоже, но не то
- Битовые манипуляции (Bit manipulation)
Оба работают с самим числом. Та страница про отдельные биты.
- Хеш-множество / словарь (Hash set / map)
Множество простых чисел всё равно надо как-то построить. Решето и есть способ его построить.
- Динамическое программирование (1-D) (Dynamic programming (1-D))
Формула отвечает сразу там, где динамика заполняет таблицу. Сначала поищите замкнутую форму.
- Префиксные суммы (Prefix sums)
Префиксные суммы отвечают по сохранённым значениям. Здесь ответ следует из свойств самих чисел.
НОД стоит O(log от меньшего значения). Решето до 1e7 нормально, а до 1e9 уже нет.
На LeetCode
Задачи, где нужны все простые до какой-то границы, например подсчёт простых или поиск пар простых в диапазоне. Решето вычёркивает кратные, начиная с p^2, и отвечает за O(n log log n).
Построй решето ниже n и посчитай true. n до 5 * 10^6, так что проверять каждое число отдельно слишком медленно.
Посчитай простые до n решетом, потом перемножь факториалы числа простых и числа остальных по модулю 10^9 + 7.
Построй решето до right, пройди по простым между left и right и запомни пару с наименьшим промежутком.
Построй решето до n, потом для каждого простого x до n / 2 проверь, простое ли n минус x.