素数筛法

2017年02月23日 12点热度 0人点赞 0条评论

题目描述

区间质数个数

输入输出格式

输入格式:

一行两个整数 询问次数n,范围m

接下来n行,每行两个整数 l,r 表示区间

输出格式:

对于每次询问输出个数 t,如l或r∉[1,m]输出 Crossing the line

输入输出样例

输入样例#1:

2 5
1 3
2 6
输出样例#1:

2
Crossing the line

说明

【数据范围和约定】

对于20%的数据 1<=n<=10 1<=m<=10

对于100%的数据 1<=n<=1000 1<=m<=1000000 -10^9<=l<=r<=10^9 1<=t<=1000000

#include
#include
using namespace std;
bool vis[10000001]={0,1};
int s[10000001]={0};
int main(){
    int n,m,l,r,ans=0;
    scanf("%d%d",&n,&m);
    for(int i=2;i*i<=m;i++)
    if(!vis[i])
    for(int j=i*i;j<=m;j+=i)
    vis[j]=1;
    for(int i=2;i<=m;i++)
    if(!vis[i]) s[i]=s[i-1]+1;
    else s[i]=s[i-1];
    while(n--){
        ans=0;
    scanf("%d%d",&l,&r);
    if(l<1||r>m||l>m){
        printf("Crossing the linen");
        continue;
    }
    printf("%dn",s[r]-s[l-1]);
    }
    return 0;
}
未经允许不得转载!素数筛法

update

纸上得来终觉浅, 绝知此事须躬行。