Sieve of Eratosthenes on the segment: Sometimes you need to find all the primes that are in the range [L...R] and not in [1...N], where R is a large number.
Conditions: You are allowed to create an array of integers with size (R−L+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 of 'j' in second for loop??
Thanks in advance!!