RezRhyme's blog

By RezRhyme, history, 3 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

 » 3 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.
•  » » 3 hours ago, # ^ |   0 Segmented sieve algorithm to generate prime numbers. If you know such blog that explains it well enough, then please share.
 » 3 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.