RezRhyme's blog

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

»
5 days 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.

  • »
    »
    2 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    • »
      »
      »
      42 hours ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      https://codeforces.com/blog/entry/46620

      Try 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, # |
  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.

  • »
    »
    27 hours 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) ?

    • »
      »
      »
      26 hours 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...

      • »
        »
        »
        »
        4 hours 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) ?

        • »
          »
          »
          »
          »
          4 hours 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