萌新求助,WA
查看原帖
萌新求助,WA
373327
EggShell123楼主2020/9/4 21:35

rt,萌新 WA 的一声枯了

#include <bits/stdc++.h>
#define ll long long

using namespace std;

const int N = 1e5;
const int inf = 0x3f3f3f3f;

bool is[N];
ll prime[N];
int cnt;

void init() {
	memset(is, true, sizeof is);
	for(int i = 2; i < (1 << 16); i++) {
		if(is[i]) {
			prime[++cnt] = i;
			for(int j = i * 2; j < (1 << 16); j += i) {
				is[j] = false;
			}
		}
	}
}

bool Prime(ll x) {
	for(int i = 1; i <= cnt && prime[i] * prime[i] <= x; i++) {
		if(x % prime[i] == 0 && x != prime[i]) return false;
	}
	return true;
}

int main() {
	ll l, r;
	int mx = -1, mn = inf;
	ll mx1, mx2, mn1, mn2;
	init();
	while(~scanf("%lld%lld", &l, &r)) {
		mx = -1, mn = inf;
		ll last = -1;
		for(ll i = l; i <= r; i++) {
			if(Prime(i)) {
				if(last != -1) {
					int now = i - last;
					if(mn > now) mn = now, mn1 = last, mn2 = i;
					if(mx < now) mx = now, mx1 = last, mx2 = i;
				}
				last = i;
			}
		}
		if(mx == -1) puts("There are no adjacent primes.");
		else printf("%lld,%lld are closest, %lld,%lld are most distant.\n", mn1, mn2, mx1, mx2);
	}
	return 0;
}
2020/9/4 21:35
加载中...