0165-Lottery

http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=0165&lang=jp
結局のところ区間内の素数の個数を数える問題に集約される。
篩を使って数えれば問題なし。
実装(C++/インクルード部分省略)

#define PRIMEMAX 1000000
//この数値未満の素数をすべて求めます
int PrimeCount[1000000*2];
bool GetedPrime=false; //すでに素数を求めたかどうか
char Prime[PRIMEMAX];//0なら素数、1なら素数ではない
void EratosthenesSieve(){
	if(GetedPrime==true) return;
	int NeedCount=(int)sqrt(PRIMEMAX)+1;
	Prime[0]=1;
	Prime[1]=1;
	//2の倍数は素数ではない
	Prime[2]=0;
	for(int i=2;i<NeedCount;i++){
		if(Prime[i]==0){
			for(int j=i*2;j<PRIMEMAX;j+=i)
				Prime[j]=1;
		}
	}
	GetedPrime=true;
}
//n以下の素数の個数
void GetPrimeCount(){
	EratosthenesSieve();
	PrimeCount[0]=0;
	for(int i=1;i<1000000;i++){
		PrimeCount[i]=PrimeCount[i-1]+1-Prime[i];
	}
	for(int i=1000000;i<=2000000;i++){
		PrimeCount[i]=PrimeCount[i-1];
	}
}
int main(){
	EratosthenesSieve();
	GetPrimeCount();
	int n,p,m,X;
	for(;;){
		scanf("%d",&n);
		if(n==0) break;
		X=0;
		for(int i=0;i<n;i++){
			scanf("%d%d",&p,&m);
			X+=PrimeCount[p+m]-PrimeCount[max(0,p-m-1)]-1;
		}
		printf("%d\n",X);
		fflush(stdout);
	}
	return 0;
}