HIT 1867 经理的烦恼

题目链接：http://acm.hit.edu.cn/hoj/problem/view?id=1867

每次更新时判断是否素数，如果从非素数变成素数就Update(x, 1)，如果从素数变成非素数就Update(x, -1)。

 /*HIT 1867
 经理的烦恼
 */
 #include<cstdio>
 #include<cstring>
 const int N=; int a[N],c[N],n,m,C;
 int prime(int num)
 {
     int i;
     if(num<=)return ;
     for(i=; i*i<=num; i++)
     {
         if(num%i==)
             return ;
     }
     return ;
 }
 int lowbit(int x)
 {
     return x & (-x);
 } void update(int i,int m)
 {
     while(i<=C)
     {
         c[i] += m;
         i += lowbit(i);
     }
 }
 int Sum(int num)
 {
     int s =;
     while(num>)
     {
         s += c[num];
         num -= lowbit(num);
     }
     return s;
 }
 int main()
 {
     //freopen("1867.txt","r",stdin);
     int i,j,k,x,y,t,time=;
     while(scanf("%d %d %d",&C,&n,&m)!=EOF)
     {
         if(C==&&n==&&m==) break;
         t = prime(m);
         memset(c,,sizeof(c));
         for(i=; i<=C; i++)
         {
             if(t!=)
             {
                 update(i,);
             }
             a[i]=m;
         }
         printf("CASE #%d:\n",++time);
         for(i=; i<n; i++)
         {
             scanf("%d %d %d",&k,&x,&y);
             if(k==)
             {
                 int tmp = a[x];
                 a[x]+=y;
                 if(prime(a[x]))
                 {
                     if(!prime(tmp))
                         update(x,);
                 }
                 else
                 {
                     if(prime(tmp))
                         update(x,-);
                 }             }
             else
                 printf("%d\n",Sum(y)-Sum(x-));
         }
         printf("\n");     }
     return ;
 }