LightOJ - 1197 区间素数筛模版

// LightOJ - 1197 区间素数筛
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn = 500000;
bool sprime[maxn],prime[maxn];
int solve(ll a,ll b){
	memset(sprime,0,sizeof(sprime));
	memset(prime,0,sizeof(prime));
	for(int i=2;(ll)i*i<b;i++){
		if(!sprime[i]){
			//素数筛小区间 [2,sqrt(b)]素数 
			for(int j=2*i;(ll)j*j<b;j+=i){
				sprime[j] = true;
			}
			for(int j=max(2ll,(a+i-1)/i)*i;j<=b;j+=i){
				prime[j-a] = true;
			}
		}
	}
	int ans = 0;
	for(int i=0;i<=b-a;i++){
		if(!prime[i])ans++;
	}
	return ans;
}
int main()
{
	int cnt=1,t,ans;
	ll a,b;
	scanf("%d",&t);
	while(t--){
		scanf("%lld %lld",&a,&b);
		ans = solve(a,b);
		if(a==1)ans--;//1不是素数 
		printf("Case %d: %d\n",cnt++,ans);	
	}
	return 0;
}
/*
3		ans:
2 36	11
3 73	20
3 11	4
*/