前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >LightOJ - 1197 区间素数筛模版

LightOJ - 1197 区间素数筛模版

作者头像
用户2965768
发布2019-08-01 10:12:41
2590
发布2019-08-01 10:12:41
举报
文章被收录于专栏:wym

给t给样例,每个样例a,b两个数,求区间[a,b]内素数的个数,(1 ≤ a ≤ b < 2^31, b - a ≤ 100000).

区间很大,区间差不大

代码语言:javascript
复制
// 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
*/
本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2019年07月13日,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档