Сито Эратосфена на сегмент

Question

Сито Эратосфена на сегмент

Сито Эратосфена на сегменте:
Иногда вам нужно найти все простые числа, которые находятся в диапазоне
[L … R], а не в [1 … N], где R — большое число.

условия:
Вы можете создать массив целых чисел с размером
(R-L + 1).

Реализация:

bool isPrime[r - l + 1]; //filled by true
for (long long i = 2; i * i <= r; ++i) {
for (long long j = max(i * i, (l + (i - 1)) / i  * i); j <= r; j += i) {
isPrime[j - l] = false;
}
}
for (long long i = max(l, 2); i <= r; ++i) {
if (isPrime[i - l]) {
//then i is prime
}
}

Какова логика установки Нижний предел из ‘J’ в второй цикл??

Заранее спасибо!!

3

algorithm c++primes sieve sieve-of-eratosthenes

Решение

Другие решения

Других решений пока нет …

Источник

Accepted Answer

Подумай о том, что мы хотим найти. Игнорировать я * я часть. У нас есть только
(L + (i — 1)) / i * i) рассмотреть. (Я написал букву L, так как l и 1 выглядят очень похоже)

Что это должно быть? Очевидно, это должно быть наименьшее число в L..R, которое делится на i. Вот когда мы хотим начать просеивать.

Последняя часть формулы / i * i находит следующее меньшее число, которое делится на i, используя свойства целочисленного деления.

Пример: 35 деление 4 * 4 = 8 * 4 = 32, 32 — наибольшее число, которое (равно или) меньше 35, которое делится на 4.

Очевидно, L — это то место, с которого мы хотим начать, и + (i-1) гарантирует, что мы не найдем наибольшее число, равное или меньшее, но наименьшее число, равное или большее, чем L, которое делится на i.

Пример: (459 + (4-1)) div 4 * 4 = 462 div 4 * 4 = 115 * 4 = 460.

460> = 459, 460 | 4, наименьшее число с этим свойством

(max (i * i, …) только для того, чтобы я сам не просеивался, если он находится в пределах L..R, я думаю, хотя мне интересно, почему это не 2 * i)

Для удобства чтения я сделал эту функцию встроенной next_divisible(number, divisor) или т.п. И я бы дал понять, что используется целочисленное деление. Если нет, то кто-нибудь умный может изменить его на обычное деление, с которым это не сработает.

Кроме того, я настоятельно рекомендую обернуть массив. Внешне не очевидно, что свойство для числа X хранится в позиции X — L. Что-то вроде класса RangedArray это делает этот сдвиг для вас, позволяя вам непосредственно вводить X вместо X — L, легко может взять на себя ответственность. Если вы этого не сделаете, по крайней мере, сделаете его вектором вне самого внутреннего класса, вы не должны использовать необработанные массивы в C ++.

2