素数：一个数 n ，若不能在[2,n-1]中找到一个能整除 n 的数 d ，则 n 为素数。

试除法判断素数

时间复杂度：

bool is_prime(int n) {
    if (n <= 1) return false;
    for(int i = 2; i * i <= n; ++ i) {
        if (n % i == 0) return false;
    }
    return true;
}

埃氏筛法

时间复杂度：
原理：每次筛出一个素数 x，并把 x 的倍数筛出。
注：对于 [ 2 * i，i * i ] 之间的合数会被比 i 更小的素数筛去，所以 j = i * i, 但要防止爆int。

const int maxn = 1e7+1;
const int maxm = 664579 + 1;

bool vis[maxn];
int prime[maxm];  // 1~1e7 中素数个数为 664579

void E_sieve(int n) { // 埃氏筛
    int tot = 0;
    for(int i = 1; i <= n; ++ i) vis[i] = 0;
    for(long long i = 2; i <= n; ++ i) {
        if (vis[i]) continue;
        prime[++tot] = i;
        for(long long j = i * i; j <= n; j += i) {
            vis[j] =  1;
        }
    }
    return tot;
}

欧拉筛（线性筛）

时间复杂度：
原理：每个合数都是由它的最小质因子筛去。
注： if (i % prime[j] == 0) break; 保证了一个数不会被重复筛去。

const int maxn = 1e8+1;
const int maxm = 5761455 + 1;

bool vis[maxn];
int prime[maxm];  // 1~1e8 之间素数个数为 5761455

int E_sieve(int n) { // 欧拉筛
    int tot = 0;
    for(int i = 1; i <= n; ++ i) vis[i] = 0;
    for(long long i = 2; i <= n; ++ i) {
        if (!vis[i]) prime[++tot] = i;
        for(int j = 1; i * prime[j] <= n; ++ j) {
            vis[i * prime[j]] = 1;
            if (i % prime[j] == 0) break;
        }
    }
    return tot;
}

区间筛

const int maxn = 1e6+1;

bool vis[maxn];
int prime[maxn];

int E_sieve(int n) { // 线性筛
    int tot = 0;
    for(int i = 1; i <= n; ++ i) vis[i] = 0;
    for(long long i = 2; i <= n; ++ i) {
        if (!vis[i]) prime[++tot] = i;
        for(int j = 1; i * prime[j] <= n; ++ j) {
            vis[i * prime[j]] = 1;
            if (i % prime[j] == 0) break;
        }
    }
    return tot;
}

int S_sieve(long long l, long long r) { // 区间筛（埃氏筛）
    int tot = E_sieve(sqrt(r));
    for(long long i = l; i <= r; ++ i) vis[i-l+1] = 0;
    for(int i = 1; i <= tot; ++ i) {  // 用2~sqrt(r)素数筛去l~r之间的素数
        long long t = prime[i];
        if (t * t > r) break;
        long long j = max((l+t-1)/t*t, 2*t); // 素数本身不能被筛
        for(; j <= r; j += t) vis[j-l+1] = 1;
    }
    int res = 0;
    for(long long i = max(l,2ll); i <= r; ++ i) // 1 不是素数
        if (!vis[i-l+1]) res ++;
    return res;
}