筛素数,求区间内素数个数

问题 1525: [蓝桥杯][算法提高VIP]找素数

时间限制: 1Sec 内存限制: 128MB 提交: 1179 解决: 133

题目描述
给定区间[L, R] , 请计算区间中素数的个数。

数据规模和约定
2 < = L < = R < = 2147483647 R-L < = 1000000
输入
两个数L和R。
输出
一行,区间中素数的个数。
样例输入
2 11
样例输出
5

解题报告:用sqrt(r)以内的数筛掉r以内的所有合数,因为区间小于等于1e6开这么大的数组就够了,数组下标记录的是这个数和l的相对差。注意该题的大优化。

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<map>
#include<vector>
#include<queue>
#include<set>
#define IL inline
#define x first
#define y second
typedef long long ll;
using namespace std;
const	int N=1000010;
bool f[N];
bool t[N];
void init(ll l, ll r)
{
	for(ll i=2;i*i<=r;i++)
	{
		if(!f[i])
		{
			for(ll j=2*i;j*j<=r;j+=i)
			f[j]=1;
			ll j=2*i;
			if(j<l)
				{
				j+=(l-j)/i*i;//大优化 
				}
			for(;j<r;j+=i)
			{
				t[j-l]=true;
			}
		}
	}
}
int main()
{
	ll l,r;
	cin>>l>>r;
	init(l,r+10);
	ll cnt=0;
	for(ll i=l;i<=r;i++)
	if(!t[i-l])	cnt++;
	cout<<cnt<<endl;
    return 0;
}




全部评论

相关推荐

来个大佬救一下,为上投了都是石沉大海了,没实习经历的话怕秋招直接进不了面。什么实习这么难找,基本
心态爆炸了:现在正式的岗位都少,实习基本不咋招的,除了大厂,中小企业其实没那么多岗位需求,就算是有,大多都是招一两个廉价劳动力,同时,他们也会希望你一来就能干活的,没时间培训你,就让你了解公司的项目,你了解完就可以开始干活。再者是,很多低质量的实习其实用处没有那么大的。我去年也是找实习找到破防,最后去了一家深圳的小公司实习,工作对我来说很简单,甚至不如我在学校做的项目,秋招的时候,这段实习经历也并没有帮上什么忙,投递简历,依旧非常低的回复率。低回复率是常态,尤其是找实习,找不到,那就把重心放在优化自己的简历和项目,多看八股文,锻炼自己的面试能力,多看别人的面经,自己模拟面试,等秋招的时候,只要有那么寥寥几次,好好抓住那几次机会。
点赞 评论 收藏
分享
求offer的大角牛:不吃香菜
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务