2276.cpp

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

/*  This Code is Submitted by wywcgs for Problem 2276 on 2006-06-14 at 16:34:31 */ 
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;

typedef unsigned int uint;
const uint PN = 48000;
const int K = 1 << 15;

bool prime[PN];
uint p[PN], pn = 0;
int zp[K];

int main()
{
	uint l, r, i, j;
	
	memset(prime, true, sizeof(prime));
	prime[0] = prime[1] = false;
	for(i = 2; i < PN; i++) {
		if(!prime[i]) continue;
		p[pn++] = i;
		for(j = i<<1; j < PN; j += i) prime[j] = false;
	}
	while(scanf("%u %u", &l, &r) != EOF) {
		int cpn = 0, c = l, mid = (int)sqrt(r*1.0)+1;
		memset(zp, 0, sizeof(zp));
		for(i = 1; i < pn && p[i] <= mid; i++) {
			uint x = (l+p[i]-1)/p[i], b = max(x, (uint)2)*p[i];
			for(j = b; j <= r; j += p[i]) zp[(j-l)>>5] |= 1<<((j-l)&31);
		}
		if(l == 2) cpn++;
		if(!(l&1)) c = l+1;
		for(i = c; i <= r; i += 2)
			if(!(zp[(i-l)>>5]&(1<<((i-l)&31)))) cpn++;
		printf("%d\n", cpn);
	}
	
	return 0;
}