题解思路：用O（sqrt（n））判断是不是素数，然后直接套数组数组。（我就奇怪了为什么还要C=0这种操作，我判断循环写&&C不行，C+n+m才行）
代码：
#include<algorithm> #include<cstdio> #include<cstring> #include<iostream> #include<cmath> #define lson l,mid,rt<<1 #define rson mid+1,r,rt<<1|1 #define inf 0x3f3f3f3f using namespace std; typedef long long ll; const int mx = 1e6+100; int n,m,C,sum[mx],num[mx]; inline int lowbit(int x){ return x&(-x); } bool vis[mx]; bool isprime(int x){ if(x<2) return 0; int cnt = sqrt(1.0*x); for(int i=2;i<=cnt;i++) if(x%i==0) return 0; return 1; } void add(int x,int v){ for(int i=x;i<=C;i+=lowbit(i)) sum[i]+=v; } int getsum(int x){ int ans = 0; while(x){ ans+=sum[x]; x-=lowbit(x); } return ans; } int main(){ int cas = 1; while(scanf("%d%d%d",&C,&n,&m)&&C+n+m){ bool v = isprime(m); for(int i=1;i<=C;i++) sum[i] = 0, vis[i] = v, num[i] = m; if(v) for(int i=1;i<=C;i++) add(i,v); printf("CASE #%d:\n",cas++); while(n--){ int x,y,z; scanf("%d%d%d",&x,&y,&z); if(x) printf("%d\n",getsum(z)-getsum(y-1)); else{ bool u = isprime(num[y]+z); add(y,u-vis[y]); vis[y] = u; num[y]+=z; } } puts(""); } return 0; }