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!

Which lines? If you want to learn about the formula to find prime numbers i was reading a blog on a site a couple days ago. Im not that experienced in Cp but that explained it pretty well.

Segmented sieve algorithm to generate prime numbers. If you know such blog that explains it well enough, then please share.

start_idx is the index in the array you want to start marking from, (start + p — 1)/p is basically ceil(start/p)...but writing in this way is better.

max_index is just an optimization over start_idx, as numbers upto p*(p-1) will be already marked so they want to start from p*p or start_idx, which ever is more. Also start is subtracted so to bring it in array range.