蒜头君请你求出区间 [l,r][l,r] [l,r][l,r] 上距离最近的相邻的素数对和距离最远的相邻的素数对。3,53,5 3,53,5 是相邻的素数,2,52,5 2, 52,5 不是相邻的素数。距离定义为 22 22 个素数的差的绝对值。比如5,7 距离为 2。
输入格式
输入 22 22 个整数 l,r(1≤l≤r≤8000000)l,r(1≤l≤r≤8000000) l, r(1 \le l \le r \le 8000000)l,r(1≤l≤r≤8000000)
输出格式
如果 a,b(ab)a,b(ab) a, b(ab)a,b(ab) 是距离最近的素数对,c,d(cd)c,d(cd) c,d(cd)c,d(cd) 是距离最远的素数对,按照如下格式输出a,b are closest, c,d are most distant.。
如果最近或者最远有多对,输出 aa aa 和 cc cc 最小的。如果没有相邻是素数对,输出There are no adjacent primes.。
3,5 are closest, 3,5 are most distant.
14 17
There are no adjacent primes.
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
#define MAX 8000004
typedef int ll;
ll map[MAX];
ll is_prime(ll m)
{
map[1]=1;
map[0]=1;
for(ll i = 2;i*i<m;++i)
{
if(!map[i])
{
for(ll j=i*i;j<=m;j+= i)
{
map[j]=1;
}
}
}
}
int main()
{
ll n,m,i,count=0;
cin>>n>>m;
if(n>m)
{
n^=m;
m^=n;
n^=m;
}
is_prime(m);
vector<ll> a;
for(i=n;i<=m;++i)
{
if(!map[i])
{
a.push_back(i);
}
}
int far=0,shortly=MAX,flag=0;
i=0;
int far_x=0,far_y=0,short_x=0,short_y=0;
// cout<<a.size()<<endl;
for(;i+1<a.size();i++)
{
if((a[i+1]-a[i])>far)
{
flag=1;
far_x=a[i];
far_y=a[i+1];
far = a[i+1]-a[i];
}
if((a[i+1]-a[i])<shortly)
{
flag=1;
short_x=a[i];
short_y=a[i+1];
shortly = a[i+1]-a[i];
}
}
if(flag)
{
cout<<short_x<<","<<short_y<<" are closest,"<<far_x<<","<<far_y<<" are most distant"<<endl;
}
else
{
cout<<"There are no adjacent primes"<<endl;
}
return 0;
}
因篇幅问题不能全部显示,请点此查看更多更全内容
怀疑对方AI换脸可以让对方摁鼻子 真人摁下去鼻子会变形
女子野生动物园下车狼悄悄靠近 后车司机按喇叭提醒
睡前玩8分钟手机身体兴奋1小时 还可能让你“变丑”
惊蛰为啥吃梨?倒春寒来不来就看惊蛰
男子高速犯困开智能驾驶出事故 60万刚买的奔驰严重损毁