【蓝桥杯】素数距离
题目
蒜头君请你求出区间 <math> <semantics> <mrow> <mo> [ </mo> <mi> l </mi> <mo separator="true"> , </mo> <mi> r </mi> <mo> ] </mo> </mrow> <annotation encoding="application/x-tex"> [l,r] </annotation> </semantics> </math>[l,r] 上距离最近的相邻的素数对和距离最远的相邻的素数对。
<math> <semantics> <mrow> <mn> 3 </mn> <mo separator="true"> , </mo> <mn> 5 </mn> </mrow> <annotation encoding="application/x-tex"> 3,5 </annotation> </semantics> </math>3,5 是相邻的素数， <math> <semantics> <mrow> <mn> 2 </mn> <mo separator="true"> , </mo> <mn> 5 </mn> </mrow> <annotation encoding="application/x-tex"> 2, 5 </annotation> </semantics> </math>2,5 不是相邻的素数。距离定义为 <math> <semantics> <mrow> <mn> 2 </mn> </mrow> <annotation encoding="application/x-tex"> 2 </annotation> </semantics> </math>2 个素数的差的绝对值。比如 <math> <semantics> <mrow> <mn> 5 </mn> <mo separator="true"> , </mo> <mn> 7 </mn> </mrow> <annotation encoding="application/x-tex"> 5,7 </annotation> </semantics> </math>5,7 距离为 <math> <semantics> <mrow> <mn> 2 </mn> </mrow> <annotation encoding="application/x-tex"> 2 </annotation> </semantics> </math>2。
输入格式
输入 <math> <semantics> <mrow> <mn> 2 </mn> </mrow> <annotation encoding="application/x-tex"> 2 </annotation> </semantics> </math>2 个整数 <math> <semantics> <mrow> <mi> l </mi> <mo separator="true"> , </mo> <mi> r </mi> <mo> ( </mo> <mn> 1 </mn> <mo> ≤ </mo> <mi> l </mi> <mo> ≤ </mo> <mi> r </mi> <mo> ≤ </mo> <mn> 8000000 </mn> <mo> ) </mo> </mrow> <annotation encoding="application/x-tex"> l, r(1 \le l \le r \le 8000000) </annotation> </semantics> </math>l,r(1≤l≤r≤8000000)
输出格式
如果 <math> <semantics> <mrow> <mi> a </mi> <mo separator="true"> , </mo> <mi> b </mi> <mo> ( </mo> <mi> a </mi> <mi> b </mi> <mo> ) </mo> </mrow> <annotation encoding="application/x-tex"> a, b(ab) </annotation> </semantics> </math>a,b(ab) 是距离最近的素数对， <math> <semantics> <mrow> <mi> c </mi> <mo separator="true"> , </mo> <mi> d </mi> <mo> ( </mo> <mi> c </mi> <mi> d </mi> <mo> ) </mo> </mrow> <annotation encoding="application/x-tex"> c,d(cd) </annotation> </semantics> </math>c,d(cd) 是距离最远的素数对，按照如下格式输出a,b are closest, c,d are most distant.。
如果最近或者最远有多对，输出 <math> <semantics> <mrow> <mi> a </mi> </mrow> <annotation encoding="application/x-tex"> a </annotation> </semantics> </math>a 和 <math> <semantics> <mrow> <mi> c </mi> </mrow> <annotation encoding="application/x-tex"> c </annotation> </semantics> </math>c 最小的。如果没有相邻是素数对，输出There are no adjacent primes.。
样例输入
3 10
样例输出
3,5 are closest, 3,5 are most distant.
样例输入
14 17
样例输出
There are no adjacent primes.
题解
筛法
#include<cstdio>
#include<vector>
using namespace std;
vector<int> v;
void prepare(int n){
for(int i=0;i<=n;i++)
v.push_back(1);
for(int i=2;i*i<=n;i++)
if(v[i])
for(int j=i*i;j<=n;j+=i)
v[j] = 0;
}
int main(){
int l,r;
scanf("%d%d",&l,&r);
prepare(r);
int a = 0;
int b = 0;
int min = 99999999;
int c = 0;
int d = 0;
int max = 0;
l<2?l=2:l; // l 小于 2 置 2
for(int i=l;i<=r;i++){
if(v[i]){
for(int j=i+1;j<=r;j++){
if(v[j]){
if(j-i < min){
a = i;
b = j;
min = j-i;
}
if(max < j-i){
c = i;
d = j;
max = j-i;
}
break; // 保证相邻
}
}
}
}
if(!max)
printf("There are no adjacent primes.");
else
printf("%d,%d are closest, %d,%d are most distant.",a,b,c,d);
return 0;
}