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.
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.
Ummm....yes, I get the intuition now. But can you please tell me how p*(p-1) already marked? I mean, some numbers are already marked. But how that is numbers upto p*(p-1) ?
because p * (p — 1) has a factor smaller than p which marks it already, and actually the numbers are marked upto (p*p) — 1 but p*(p — 1) is previous divisor of p before p^2, so we talk about that...
Oh. That's why. So we just start from p*p. But why we also have to bring start_idx and why that equals ceil(start/p) ?
notice that start_idx is the first index which is is divisible by p, in the segment, also notice that we do max of p*p and start_idx so that we don't do unnecessary marking. if p*p is smaller that start then we dont need to mark divisors before start_idx
That's it! Thank you so much.