I_am_prince_VEGETA's blog

I can't understand this part of segmented sieve of Eratosthenes.
By I_am_prince_VEGETA, history, 3 years ago, In English

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!

  • Vote: I like it
  • +1
  • Vote: I do not like it

Comments Comments (7)
| Write comment?
»
3 years ago, # |
  Vote: I like it +8 Vote: I do not like it

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.

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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) ?

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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...

      → Reply
      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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) ?

        → Reply
        • »
          »
          »
          »
          »
          3 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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

          → Reply