Sieve of Eratosthenes on a segment
Sieve of eratosthenes on a segment: Sometimes you need to find all primes that are in the range [L ... R], not [1 ... N], where R is a large number.
Conditions: You are allowed to create an array of integers with size (RL + 1).
Implementation:
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
}
}
What is the logic behind setting the lower limit 'j' per second for a loop ??
Thanks in advance!
source to share
Think about what we want to find. Ignore the i * i part. We only have (L + (i - 1)) / i * i) to consider. (I wrote L-capital since l and 1 look very similar)
What should it be? Obviously, this should be the smallest number inside L..R that is divisible by i. This is when we want to start seeping.
The last part of the formula / i * i finds the next bottom number that is divisible by i using the integer division properties.
Example: 35 div 4 * 4 = 8 * 4 = 32, 32 is the highest number that is (equal to or) less than 35, which is divisible by 4.
L, where we want to start, obviously, and + (i-1), make sure we don't find the largest number equal to or less than, but the smallest number equal to or greater than L that is divisible by i.
Example: (459 + (4-1)) div 4 * 4 = 462 div 4 * 4 = 115 * 4 = 460.
460> = 459, 460 | 4, the smallest number with this property
(max (i * i, ...) only so that I don't sift myself if it's inside L..R, I guess, although I'm wondering why it's not 2 * i)
For readability reasons, I did it inline function next_divisible(number, divisor)
or the like. And I would make it clear that integer division is used. If not, someone smart might change it to a regular division that it won't work with.
Also, I highly recommend wrapping the array. It is not superficially obvious that the property for the number X is stored at position X - L. Something like a class RangedArray
that does this shift for you, allowing you to directly enter X instead of X - L, could easily take over. If you don't, at least make it a vector outside of the innermost class, you shouldn't be using raw arrays in C ++.
source to share