AOJ 0165 Lottery
問題
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0165。
解法
p-m以上p+m以下の素数数えていく。素数を用意する配列にはa[i]、i以下の素数の数を累積和で記録しておかないとTLEになる
コード
int p[MAX_P], n, sum[MAX_P]; int main(){ p[0] = p[1] = 1; REP(i, 2, MAX_P){ sum[i] = sum[i-1]; if(!p[i]){ sum[i]++; for(int j = i+i; j < MAX_P; j += i) p[j] = 1; } } while(scanf("%d", &n) && n){ int ip, m, res = 0; rep(i, n){ scanf("%d%d", &ip, &m); int top = (ip+m)>MAX_P-1?MAX_P-1:(ip+m); int under = (ip-m-1)>0?(ip-m-1):0; int c = sum[top] - sum[under]; if(c) res += c-1; else res--; } printf("%d\n", res); } return 0; }
二次元配列の累積和とかの扱い方が分からない