埃氏筛法的一般写法（区间筛法） 问题 解法
求 $[L, R]$ 之间的素数表。
解法
一个合数 $n$ 的最小素因子不超过 $sqrt{n}$。因此，在埃氏筛法的过程中，每当“新发现”一个素数 $p$，可以从 $p^2$ 筛起，而不必从 $2p$ 筛起。
先用埃氏筛法求出 $[1,lfloor sqrt{R} floor]$ 上的素数表，再在 $[L, R]$ 上用埃氏筛法求素数。
const int N(1e5); bool isprime[N]; int prime[N]; void init() { memset(isprime, -1, sizeof isprime); isprime[0] = isprime[1] = 0; int np = 0; for (int i = 0; i < N; i++) { if (isprime[i]) { prime[np++] = i; for (int j = i * i; j < N; j += i) isprime[j] = 0; } } } typedef long long ll; const int M(1e5); bool ok[M]; int res[M]; int seive(ll l, ll r) { assert(1 <= l && l <= r); memset(ok, -1, sizeof ok); if (l == 1) ok[0] = 0; //error-prone int k = sqrt(r); for (int i = 0; prime[i] <= k; i++) { ll j = (l + prime[i] - 1) / prime[i] * prime[i]; j = max(j, (ll) prime[i] * prime[i]); for (; j <= r; j += prime[i]) ok[j - l] = 0; } int np = 0; for (int i = 0; i <= r - l; i++) if (ok[i]) res[np++] = i + (ll) l; return np; }
更新：
不必先把 $[2, lfloor sqrt{R} floor]$ 上的素数存下来。更好的做法是先分别做好 $[2, lfloor sqrt{R} floor]$ 和 $[L, R]$ 的表，然后从 $[2, lfloor sqrt{R} floor]$ 的表中筛得素数的同时，也将其倍数从 $[L, R]$ 中划去。
const int N = 1e6 + 5, M = sqrt(1e9); bool is_prime[N]; // 注意：用 sqrt(1e9) + 1 作为数组大小不符合标准, sqrt(1e9) 不是编译期常量，但是 gcc 支持这样做。 bool is_prime_small[M + 1]; void segment_seive(int l, int r) { // [l, r] assert(1 <= l && l <= r); int t = sqrt(r + 0.5); for (int i = 2; i <= t; i++) is_prime_small[i] = true; for (int i = 0; i <= r - l; i++) is_prime[i] = true; if (l == 1) is_prime[0] = false; for (int i = 2; i <= t; i++) if (is_prime_small[i]) { for (int j = i * i; j <= t; j += i) is_prime_small[j] = false; for (int j = max(i * i, (l + i - 1) / i * i); j <= r; j += i) is_prime[j - l] = false; } }