### RezRhyme's blog

By RezRhyme, history, 5 days ago,

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!

• +1

 » 5 days ago, # |   +8 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.
•  » » 2 days ago, # ^ |   0 Segmented sieve algorithm to generate prime numbers. If you know such blog that explains it well enough, then please share.
•  » » » 42 hours ago, # ^ |   0 https://codeforces.com/blog/entry/46620Try this blog and follow the link. It talks about the sieve, it may look overwhelming but it's not too hard to understand. (It may take some time, it took me like 20 minutes to understand the prime factorization part)Also search on youtube. Code Chef has a good trilogy series about primes on youtube.
 » 5 days ago, # |   0 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.
•  » » 27 hours ago, # ^ |   0 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) ?
•  » » » 26 hours ago, # ^ |   0 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...
•  » » » » 4 hours ago, # ^ |   0 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) ?
•  » » » » » 4 hours ago, # ^ |   0 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