题目链接：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 ;
}