Как написать решето Эратосфена за O(n log log n) и не словить MLE на n = 10^8?
Классическое решето я знаю, но на больших границах (n до 10^8) bool sieve[N] либо ест слишком много памяти, либо я делаю что-то не так с границами цикла. Хочется канонической реализации с правильной асимптотикой и без переполнений в i*i.
vector<bool> sieve(int n) {
vector<bool> is_prime(n+1, true);
for (int i = 2; i <= n; i++)
for (int j = 2*i; j <= n; j += i)
is_prime[j] = false; // это медленно?
return is_prime;
}
Это же O(n log n), а не O(n log log n)? И почему i*i может переполниться?
2 ответа
Да, твой вариант хуже оптимального по двум причинам. Первое: вычёркивать кратные нужно только для простых i — если is_prime[i] уже false, числа i нет смысла обрабатывать. Второе: вычёркивание стоит начинать не с 2*i, а с i*i, потому что все меньшие кратные (2*i, 3*i, ..., (i-1)*i) уже вычеркнуты меньшими простыми. Именно эти два улучшения дают суммарную сложность O(n log log n) по времени (сумма n/p по простым p ведёт себя как n·ln ln n).
vector<bool> sieve(int n) {
vector<bool> is_prime(n + 1, true);
is_prime[0] = is_prime[1] = false;
for (int i = 2; (long long)i * i <= n; i++)
if (is_prime[i])
for (int j = i * i; j <= n; j += i)
is_prime[j] = false;
return is_prime;
}
Про переполнение: i*i при i около 46341 уже вылезает за int (~2.1·10^9). Поэтому в условии цикла обязательно приводи к long long: (long long)i * i <= n. Внутри j = i*i тоже опасно, если n близко к INT_MAX — лучше держать n в пределах ~2·10^9 или брать j как long long.
По памяти vector<bool> упакован по битам, поэтому 10^8 ≈ 12 МБ — проходит. Память O(n) бит.
Добавлю частую оптимизацию для совсем больших границ — сегментированное решето. Когда даже битовый массив на 10^9 не лезет, ты сначала находишь все простые до sqrt(n) обычным решетом, а потом обрабатываешь отрезок [L, R] размером с кеш (например, 32768) этими простыми. Память становится O(sqrt(n) + размер блока), а время остаётся O(n log log n). Это стандартный приём, когда нужно перечислить простые на отрезке, который сам по себе огромен.