Что решает
простые числа
Статьи
NUM
Алгоритм
Решето Эратосфена
Все простые до n за O(n log log n): вычёркиваем кратные каждого простого, начиная с его квадрата.
O(n log log n)
2 задачи
NUM
Алгоритм
Тест Миллера — Рабина
Простота числа за k возведений в степень: основания-свидетели ловят составное, лжецов не больше четверти.
O(k log³ n)
2 задачи
Задачи
Часто рядом
теория чисел 2 безопасность 2 классика 2 олимпиады 2 предподсчёт 1 массив 1 дружит с кэшем 1 случайность 1 в проде 1