I_am_prince_VEGETA's blog

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!

Full text and comments »

By I_am_prince_VEGETA, history, 3 years ago, In English

Here's the problem:

166A - Ранклист

The same codes are having different verdicts here,

submission:113596205

113554437 (WA on test 15)

113536634 (WA on test 15)

Accepted one is in C++17(64). Rest two are in C++17 and C++14. I use sublime text and Your text to link here... Both gives correct output for test 15 in C++14 and other versions. But This problem's verdict and custom invocation shows me wrong. I wonder what's the deal here?

Full text and comments »