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; }