I can't understand this part of segmented sieve of Eratosthenes.

Правка en1, от I_am_prince_VEGETA, 2021-06-10 21:11:52

From here I am trying to learn segmented sieve. But cannot get these two lines of the code part:

int count_primes(int n) { const int S = 10000;

vector<int> primes;
int nsqrt = sqrt(n);
vector<char> is_prime(nsqrt + 1, true);
for (int i = 2; i <= nsqrt; i++) {
    if (is_prime[i]) {
        primes.push_back(i);
        for (int j = i * i; j <= nsqrt; j += i)
            is_prime[j] = false;
    }
}

int result = 0;
vector<char> block(S);
for (int k = 0; k * S <= n; k++) {
    fill(block.begin(), block.end(), true);
    int start = k * S;
    for (int p : primes) {
        int start_idx = (start + p - 1) / p;  //This line
        int j = max(start_idx, p) * p - start;  //This line
        for (; j < S; j += p)
            block[j] = false;
    }
    if (k == 0)
        block[0] = block[1] = false;
    for (int i = 0; i < S && start + i <= n; i++) {
        if (block[i])
            result++;
    }
}
return result;

}

I see it works, but don't get how and why it works. What's the logic or intuition here? Please somebody help me out!

Теги #eratosthenes_sieve, segmented sieve, #sieve, #number theory

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en1 Английский I_am_prince_VEGETA 2021-06-10 21:11:52 1336 Initial revision (published)