记录编号	566575	评测结果	AAAAAAAAAA
题目名称	[POJ 2689]质数距离	最终得分	100
用户昵称	yrtiop	是否通过	通过
代码语言	C++	运行时间	0.558 s
提交时间	2021-11-13 10:25:08	内存使用	12.54 MiB

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
const int maxn = 1000005;
bool val[maxn];
int prime[maxn],cnt;
int p[maxn],tot;
bool flag[maxn];
int L[maxn],R[maxn];
int main() {
	freopen("primedistance.in","r",stdin);
	freopen("primedistance.out","w",stdout);
	int maxR = 0;
	int m = 0;
	while(~ scanf("%d %d",&L[m + 1],&R[m + 1]))++ m,maxR = max(maxR , R[m]);
	int n = sqrt(maxR);
	flag[0] = flag[1] = true;
	for(int i = 2;i <= n;++ i) {
		if(!flag[i]) {
			prime[++ cnt] = i;
		}
		for(int j = 1;j <= cnt&&(long long)prime[j] * i <= n;++ j) {
			flag[i * prime[j]] = true;
			if(!(i % prime[j])) {
				break ;
			}
		}
	}
	for(int i = 1;i <= m;++ i) {
		tot = 0;
		int l = L[i],r = R[i];
		memset(val , false , sizeof(val));
		for(int j = 1;j <= cnt;++ j) {
			for(int k = max(2 , !(l % prime[j]) ? l / prime[j] : l / prime[j] + 1);k <= r / prime[j];++ k) {
				val[prime[j] * k - l] = true;
			}
		}
		for(int k = l;k <= r;++ k) {
			if(!val[k - l])p[++ tot] = k;
		}
		if(tot < 2) {
			printf("There are no adjacent primes.\n");
			continue ;
		}
		int minD = 0x7fffffff,maxD = -1;
		int minl = 0,minr = 0,maxl = 0,maxr = 0;
		for(int k = 1;k < tot;++ k) {
			int dis = p[k + 1] - p[k];
			if(dis > maxD) {
				maxD = dis;
				maxl = p[k];
				maxr = p[k + 1];
			}
			if(dis < minD) {
				minl = p[k];
				minr = p[k + 1];
				minD = dis;
			}
		}               
		printf("%d,%d are closest, %d,%d are most distant.\n",minl,minr,maxl,maxr);
	}
	return 0;
}