Решето Эратосфена
Узнайте о решете Эратосфена
Введение
Нам дан диапазон чисел , и нам нужно найти все простые числа в этом диапазоне.
Например, в диапазоне
простые числа:
Узнайте о решете Эратосфена
Нам дан диапазон чисел , и нам нужно найти все простые числа в этом диапазоне.
Например, в диапазоне
простые числа:
Классический алгоритм для этой задачи — решето Эратосфена.
При обработке чисел в диапазоне мы можем сразу помечать все кратные текущего простого числа как составные.
Например:
2, мы можем пометить все кратные 2 как составные;3, мы можем пометить все кратные 3 как составные;Это позволяет нам постепенно исключить все непростые числа.
Вспомним важный факт: если число составное, то у него есть простой делитель не больше .
Следовательно, чтобы найти все простые числа до , достаточно выполнять процесс просеивания только числами до .
Мы создаём массив prime, где:
prime[x] = true означает, что x в данный момент считается простым;prime[x] = false означает, что x составное.Изначально все числа помечены как простые, кроме 0 и 1.
Затем для каждого числа i от 2 до :
i всё ещё помечено как простое, то пометить все кратные i как составные.Внутренний цикл начинается с , потому что все меньшие кратные уже были обработаны ранее.
Например, если мы на i = 5, то:
10 = 2 \cdot 5 уже было помечено при обработке 2;15 = 3 \cdot 5 уже было помечено при обработке 3;20 = 4 \cdot 5 уже было помечено ещё раньше.Так что первое новое кратное, которое нужно пометить, — это .
В некоторых задачах значение может переполнить тип int.
В таких случаях безопаснее привести i к long long перед умножением.
Например:
int n;
vector<bool> prime(n + 1, true);
prime[0] = prime[1] = false;
for (int i = 2; i * i <= n; ++i) {
if (prime[i]) {
for (int j = i * i; j <= n; j += i) {
prime[j] = false;
}
}
}
for (int i = 2; 1LL * i * i <= n; ++i) {
...
}