----------------------- [00000000000] <-- sqrt(N)

[L..R]  // R <= N

pn, p[] // primes <= sqrt(N)
is[R - L + 1];

// Len = R - L + 1
// Memory = Len = sqrt(N)
// Time >= sqrt(N) / log(N)
// Time = sqrt(N) / log(N) + Len * (?) -- упражнение

// Len >= sqrt(N) / log(N)

int z = sqrt(N);
int pn, p[z]; // Я уже посчитал простые числа <= sqrt(N)
int is[z];
int x[z];

memcpy(x, p, sizeof(p)); // x[i] >= L
for (int L = 0; L <= N; L += z)
{
  R = min(N, L + z - 1);
  memset(is, 0, sizeof(is));
  for (i = 0; i < pn; i++) // sqrt(N) / log(N)
  {
    for (; x[i] <= R; x[i] += p[i])
      is[x[i] - L] = 1;
  }
}