学步园

#include<cstdio>
#include<cstring>
#define MAXN 100005
 
int num[MAXN];
bool is_prime[MAXN];//is_prime[i] = 1 表示i是质数
void solve() {
   memset(is_prime, true, sizeof(is_prime));
   is_prime[0] = is_prime[1] = false;
   num[0] = num[1] = 0;
   for(int i = 2; i < MAXN; ++ i) {
      if(is_prime[i]) {
         num[i] = num[i - 1] + 1;
         for(int j = i+i; j < MAXN; j += i) {
            is_prime[j] = false;
         }
      } else {
         num[i] = num[i - 1];
      }
   }
}
 
int main() {
   freopen("poj3978.txt", "r", stdin);
   solve();
   int a, b;
   while(scanf("%d%d", &a, &b) && a != -1) {
      if(is_prime[a]) {
         printf("%d\n", num[b] - num[a] + 1);
      } else {
         printf("%d\n", num[b] - num[a]);
      }
   }
   return 0;
}