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

loaky · 2018-09-21 11:07:19 · 题解

素数判断，许多dalao已经说了，我们首先先是线性筛，筛出sqrt(r)内的所有素数，用这些素数又来筛l到r，因为如果直接记录l到r区间内某个数是否为整数，用数组不得行，可以用map存，我这里是重新开了个数组把l到r这段区间重新从1开始编号，这里用了个ceil意思是大于等于当前值得最小整数，也就是向下取整，然后就分别用每个素数去筛把！

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;
const int maxn=10000000;
const int inf=10000000;
long long n,m,ans;
long long idx=1,prem[inf];
bool fl[inf],ins[inf];
int main(){
    scanf("%lld%lld",&n,&m);
    fl[1]=0;
    for(int i=2;i<=50005;i++){
        if(fl[i]==0){
            prem[idx]=i;
            idx++;
        }
        for(int j=1;j<idx&&prem[j]*i<=50005;j++){
            fl[i*prem[j]]=1;
            if(i%prem[j]==0) break;
        }
    }
    long long p,q;
    for(int i=1;i<=idx;i++){
        if(prem[i]>m)break;
        p=ceil(n*1.0/prem[i]),q=ceil(m*1.0/prem[i]);
        if(p==1)p=2;
        for(int j=p;j<=q&&prem[i]*j<=m;j++)
            ins[prem[i]*j-n+1]=1;
    }
    int tot=0;
    for(int i=1;i<=m-n+1;i++) if(!ins[i]) tot++;
    cout<<tot;
    return 0;
}