题目链接：

洛谷P1835 素数密度

题目大意：

给定区间[L，R],(L≤R≤2147483647,R-L≤1000000)，请计算区间中素数的个数。

#include <bits/stdc++.h>
using namespace std;
const int N = 5e4 + 50;
const int LEN = 1e6 + 50;
int L, R;
// 先线性筛出50000以内质数
int prime[N], num[N], tot;
void init() {
    for(int i = 2; i < N; i++) {
        if(!num[i]) {
            prime[++tot] = i;
        }
        for(int j = 1; j <= tot && prime[j] * i < N; j++) {
            num[i * prime[j]] = 1;
            if (i % prime[j] == 0) {
                break;
            }
        }
    }
}
// 再用埃筛的思想，划掉[L,R]中的合数
int notprime[LEN], prime2[N], cnt;
void work(int L, int R) {
    if (L == 1) {
        L = 2;
    }
    for (int i = 1; i <= tot && 1LL * prime[i] * prime[i] <= R; i++) {
        int x = L / prime[i] + (L % prime[i] != 0);
        if (x == 1) x++;
        for (int j = x; 1LL * j * prime[i] <= R; j++) {
            notprime[j * prime[i] - L] = 1;
        }
    }
    for (int i = 0; i <= R - L; i++) {
        if(!notprime[i]) {
            prime2[++cnt] = i + L;
        }
    }
}
int main()
{
    scanf("%d%d", &L, &R);
    init(); work(L, R);
    printf("%d\n", cnt);
    return 0;
}