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

二次元配列の累積和とかの扱い方が分からない