1552.cpp

这是哈尔滨工业大学acmOJ的源代码

/*  This Code is Submitted by wywcgs for Problem 1552 on 2006-09-04 at 10:41:37 */ 
#include <cstdio>
#include <algorithm>
using namespace std;

typedef unsigned int uint;
const int N = 1 << 15;
const uint PL = 1 << 16;

int main()
{
	bool prime[PL];
	uint zp[N], l, u, p[N], pn = 0;
	
	memset(prime, true, sizeof(prime));
	for(uint i = 2; i < PL; i++) {
		if(!prime[i]) continue;
		p[pn++] = i;
		for(uint j = 2; i*j < PL; j++) prime[i*j] = false;
	}
	while(scanf("%d %d", &l, &u) != EOF) {
		memset(zp, 0, sizeof(zp));
		if(l == 1) l++;
		for(uint i = 0; i < pn && p[i] < u; i++) {
			uint b = (l+p[i]-1)/p[i]*p[i];
			if(b == p[i]) b += p[i];
			for(uint j = b; j <= u; j += p[i])
				zp[(j-l)>>5] |= 1 << ((j-l)&31);
		}
		uint n = 0, prv = 0, minl = 1 << 30, maxl = 0, mina, minb, maxa, maxb;
		for(uint i = l; i <= u; i++)
			if(!(zp[(i-l)>>5]&(1<<((i-l)&31)))) {
				if(prv != 0) {
					if(i-prv > maxl) { maxl = i-prv; maxa = prv; maxb = i; }
					if(i-prv < minl) { minl = i-prv; mina = prv; minb = i; }
				}
				prv = i; n++;
			}
		if(n < 2) printf("There are no adjacent primes.\n");
		else printf("%u,%u are closest, %u,%u are most distant.\n", mina, minb, maxa, maxb);
	}
	
	return 0;
}