【蓝桥杯】素数距离

题目

蒜头君请你求出区间 <math> <semantics> <mrow> <mo> [ </mo> <mi> l </mi> <mo separator="true"> , </mo> <mi> r </mi> <mo> ] </mo> </mrow> <annotation encoding="application&#47;x&#45;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&#47;x&#45;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&#47;x&#45;tex"> 2, 5 </annotation> </semantics> </math>2,5 不是相邻的素数。距离定义为 <math> <semantics> <mrow> <mn> 2 </mn> </mrow> <annotation encoding="application&#47;x&#45;tex"> 2 </annotation> </semantics> </math>2 个素数的差的绝对值。比如 <math> <semantics> <mrow> <mn> 5 </mn> <mo separator="true"> , </mo> <mn> 7 </mn> </mrow> <annotation encoding="application&#47;x&#45;tex"> 5,7 </annotation> </semantics> </math>5,7 距离为 <math> <semantics> <mrow> <mn> 2 </mn> </mrow> <annotation encoding="application&#47;x&#45;tex"> 2 </annotation> </semantics> </math>2。

输入格式

输入 <math> <semantics> <mrow> <mn> 2 </mn> </mrow> <annotation encoding="application&#47;x&#45;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&#47;x&#45;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&#47;x&#45;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&#47;x&#45;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&#47;x&#45;tex"> a </annotation> </semantics> </math>a 和 <math> <semantics> <mrow> <mi> c </mi> </mrow> <annotation encoding="application&#47;x&#45;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;
}

返回目录，查看更多