记录编号	554962	评测结果	AAAAAAAAAA
题目名称	[POJ 2689]质数距离	最终得分	100
用户昵称	Oasiz	是否通过	通过
代码语言	C++	运行时间	0.544 s
提交时间	2020-09-23 19:55:16	内存使用	15.82 MiB

#include<cstdio>
#include<cstring>
#include<iostream>
#define MN 46345
#define LL long long
using namespace std;
LL tp[MN], primeLR[1000005], A, B;
bool vis[1000005];
void FF(){
	memset(tp, 0, sizeof(tp));
	for (LL i = 2; i <= MN; i++){
		if (!tp[i]) tp[++tp[0]] = i;
		for (LL j = 1; j <= tp[0] && tp[j] <= MN / i; j++){
			tp[tp[j]*i] = 1;
			if (i % tp[j] == 0) break;
		}
	}
}
void FLR(LL L, LL R){
	memset(vis, 0, sizeof(vis));
	if (L < 2) L = 2;
	for (LL i = 1; i <= tp[0] && (long long)tp[i]*tp[i] <= R; i++){
		LL s = L / tp[i] + (L % tp[i] > 0);
		if (s == 1) s = 2;
		for (LL j = s; (long long)j * tp[i] <= R; j++){
			if ((long long)j * tp[i] >= L) vis[j * tp[i] - L] = 1;
		}
	}
	primeLR[0] = 0;
	for (LL i = 0; i <= R - L; i++){
		if (!vis[i]) primeLR[++primeLR[0]] = i + L;
	}
}
int main(){
	freopen("primedistance.in","r",stdin);
	freopen("primedistance.out","w",stdout);
	FF();
	while (cin>>A>>B){
		FLR(A, B);
		if (primeLR[0] < 2){
			printf("There are no adjacent primes.\n");
		}
		else{
			LL x1 = 0, x2 = 1E8, y1 = 0, y2 = 0;
			for (LL i = 1; i < primeLR[0]; i++){
				if (primeLR[i + 1] - primeLR[i] < x2 - x1){
					x1 = primeLR[i], x2 = primeLR[i + 1];
				}
				if (primeLR[i + 1] - primeLR[i] > y2 - y1){
					y1 = primeLR[i], y2 = primeLR[i + 1];
				}
			}
			printf("%d,%d are closest, %d,%d are most distant.\n", x1, x2, y1, y2);
		}
	}
	return 0;
}