Sieve of Eratosthenes on a segment

Viewed 492

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!!

1 Answers
Related