首页 技术 正文
技术 2022年11月23日
0 收藏 774 点赞 4,938 浏览 1445 个字

http://poj.org/problem?id=2689

题目大意,给不超过int的l,r,其中r-l+1<=1000000,筛出其中的素数,并且求出相邻素数差值最大和最小的一对。

——————————————————

显然这是一道筛出l和r之间素数的裸题。

我们发现对于区间里的一个合数,其最大质因子不会超过50000(不然50000平方就大于2147483647)

秉承着正难则反的思想,筛1-50000素数,然后用一种很神奇的方法判断掉区间里的合数,统计素数即可。

判断方法:

首先我们将每个素数(记为su)平方得到t,一定是合数。

如果发现其<l。

我们就可以t=l/su*su,得到的也一定是合数。

如果此时仍然<l,我们为t+=su,得到的还是合数。

当然如果超了r那就continue;

然后对于t打标记。

然后不断地t+=su直到超r为止。

可以发现一定能够筛全合数。

简略证明:

不断地加相当于乘。

所以实际上我们在做的就是(例如su=2),就是2*2,2*3,2*4,2*5……这些全是合数。

而且因为起点是平方,所以避免了3*2这样的重复产生,所以更加的快捷。

#include<cstdio>
#include<cstring>
#include<iostream>
#include<cmath>
#include<map>
#include<algorithm>
using namespace std;
const int INF=;
int su[]={};
bool he[]={};
int cnt=;
bool vis[]={};
void Euler(int n){
for(int i=;i<=n;i++){
if(he[i]==){
cnt++;
su[cnt]=i;
}
for(int j=;j<=cnt&&i*su[j]<=n;j++){
he[su[j]*i]=;
if(i%su[j]==)break;
}
}
return;
}
int main(){
Euler();
int l,r;
while(scanf("%d%d",&l,&r)!=EOF){
memset(vis,,sizeof(vis));
int ans=;
for(int i=;i<=cnt&&su[i]<=sqrt(r);i++){
//t接下来无论怎么变都是合数
int t=su[i]*su[i];
if(t<l)t=l/su[i]*su[i];//t太小的时候就得这样让它变大点
if(t<l){
if(t<=r-su[i]){
t+=su[i];
}else continue;
}
while(t<=r){
vis[t-l]=;
if(t==su[i])vis[t-l]=;//压缩空间
if(t<=r-su[i])t+=su[i];
else break;
}
}
if(l==)vis[]=;
int p=-;
int x1,y1,x2,y2,ans1=-,ans2=INF;
for(int i=;i<=r-l;i++){
if(!vis[i]){
if(p==-){p=i;continue;}
if(ans1<i-p){ans1=i-p;x1=p+l;y1=i+l;}
if(ans2>i-p){ans2=i-p;x2=p+l;y2=i+l;}
p=i;
}
}
if(ans1==-)cout<<"There are no adjacent primes."<<endl;
else cout<<x2<<","<<y2<<" are closest, "<<x1<<","<<y1<<" are most distant."<<endl;
}
return ;
}

微信扫一扫

支付宝扫一扫

本文网址:https://www.zhankr.net/141359.html

相关推荐
python开发_常用的python模块及安装方法
adodb:我们领导推荐的数据库连接组件bsddb3:BerkeleyDB的连接组件Cheetah-1.0:我比较喜欢这个版本的cheeta…
日期:2022-11-24 点赞:875 阅读:5,071
Educational Codeforces Round 11 C. Hard Process 二分
C. Hard Process题目连接:http://www.codeforces.com/contest/660/problem/CDes…
日期:2022-11-24 点赞:806 阅读:3,505
下载Ubuntn 17.04 内核源代码
zengkefu@server1:/usr/src$ uname -aLinux server1 4.10.0-19-generic #21…
日期:2022-11-24 点赞:565 阅读:4,316
可用Active Desktop Calendar V7.86 注册码序列号
可用Active Desktop Calendar V7.86 注册码序列号Name: www.greendown.cn Code: &nb…
日期:2022-11-24 点赞:730 阅读:4,310
Android调用系统相机、自定义相机、处理大图片
Android调用系统相机和自定义相机实例本博文主要是介绍了android上使用相机进行拍照并显示的两种方式,并且由于涉及到要把拍到的照片显…
日期:2022-11-24 点赞:512 阅读:4,911
Struts的使用
一、Struts2的获取  Struts的官方网站为:http://struts.apache.org/  下载完Struts2的jar包,…
日期:2022-11-24 点赞:671 阅读:3,099
发表评论
暂无评论

还没有评论呢,快来抢沙发~

助力内容变现

将您的收入提升到一个新的水平

点击联系客服

在线时间:8:00-16:00

客服电话

400-888-8888

客服邮箱

ceotheme@ceo.com

扫描二维码

关注微信公众号

扫描二维码

手机访问本站