В чём разница между решетом Эратосфена и линейным решетом — что выбирать на олимпиаде?
Есть классическое решето Эратосфена за O(n log log n) и линейное решето Эйлера за O(n). Линейное асимптотически быстрее — значит всегда брать его? Или есть нюансы? Хочу понять, в каких задачах какое реально выгоднее.
2 ответа
Несмотря на формально лучшую асимптотику линейного решета (O(n) против O(n log log n)), на практике выбор не очевиден — log log n это крошечный множитель (для n=10^8 это ~3-4), а константа и локальность кеша решают.
Решето Эратосфена (с битовым массивом, вычёркивание от i*i):
- Память — O(n) бит (упакованный
vector<bool>/bitset), для n=10^8 это ~12 МБ. - Доступ к памяти линейный (хорошая локальность), часто быстрее на практике.
- Бери, когда нужно просто перечислить простые или иметь флаг «простое/нет».
Линейное решето Эйлера:
- Память — O(n) int (массив
lp[]наименьших простых делителей) — в ~32 раза больше Эратосфена. - Random-доступ
lp[i*p]портит кеш → по времени часто проигрывает Эратосфену. - Бери, когда нужен сам массив
lp[](быстрая факторизация запросов) или мультипликативная функция (phi, mu, число делителей) за линию.
Итог: нужны простые числа/флаги → Эратосфен. Нужен lp[] или мультипликативная функция → линейное. «Быстрее по O» не значит «быстрее по таймеру».
Добавлю практический ориентир по границам. До n ~ 10^7-10^8 оба решета пролетают за доли секунды. Если нужно работать с границей n ~ 10^9 и больше — ни то, ни другое не влезет по памяти, переходи на сегментированное решето (находишь простые до sqrt(n), потом обрабатываешь отрезки блоками по ~32 КБ под размер кеша). А если число одно и огромное (до 10^18) — решето вообще не нужно, бери факторизацию O(sqrt n) или ро-Полларда.