题解 P1835 【素数密度_NOI导刊2011提高（04）】

· · 题解

此题不少书上都有, 就是考筛法的应用. 首先由于 L, R <= MAXINT , 所以用筛法, 最大的质数不会超过 \sqrt{MAXINT} , 用线性筛预处理即可.

然后我们用埃式筛法, 从 [L, R] 中最小的某质数的倍数开始筛起, 具体实现和朴素的埃式筛差不多.

然而……

此处在循环的时候一定要注意! 一定要注意! 一定要注意! 如果用 int 类型, 会自然溢出, 然后就会莫名其妙地 RE (因为会不停地循环……). 我在此处调了一个晚上. 所以我们此处要么特判一下, 要么就改用 long \ long .如果用 long \ long 的话, 要注意数组不要开太大, 够用就好, 不然会 MLE (不要问我怎么知道的).

以下是代码: 

#include<iostream>
#include<cmath>
#include<cstring>
using namespace std;
typedef long long ll;

ll vis[1000007], notP[100007], prime[100007];
int main(){
    ll l, r;
    cin >> l >> r;
    memset(vis, 0ll, sizeof(vis));
    memset(notP, 0ll, sizeof(notP));
    ll cnt = 0ll;
    for(ll i = 2ll; i <= sqrt(r); ++i){
        if(!notP[i])
            prime[++cnt] = i;
        for(ll j = 1ll; j <= cnt; ++j){
            if(i * prime[j] > sqrt(r))
                break;
            notP[prime[j] * i] = 1ll;
            if(!i % prime[j])
                break;
        }
    }
    for(ll i = 1ll; i <= cnt; ++i){
        ll j;
        if(l % prime[i])
            j = (l / prime[i] + 1ll) * prime[i];
        else
            j = l;
        if(j == prime[i])
            j += prime[i];
        for(; j <= r; j += prime[i])
            vis[j - l] = 1ll;
    }
    ll ans = 0ll;
    for(ll i = l; i <= r; ++i)
        if(!vis[i - l])
            ++ans;
    cout << ans << endl;
    return 0;
}