树状数组+素数打表
1 #include <cstdio> 2 #include <iostream> 3 #include <string.h> 4 #include <algorithm> 5 #include <cmath> 6 using namespace std; 7 const int maxn=10000100; 8 const int maxm=1000010; 9 int c[maxm],now[maxm],k,n,m; 10 bool phi[maxn]; 11 void getphi(){ 12 memset(phi,1,sizeof(phi)); 13 int q=(int)sqrt(maxn)+1; 14 phi[0]=phi[1]=0; 15 for(int i=2;i<=q;i++){ 16 if(phi[i]){ 17 for(int j=i*2;j<maxn;j+=i) 18 phi[j]=0; 19 } 20 } 21 } 22 int lowbit(int x){return x&(-x);} 23 int sum(int b){ 24 int sum=0; 25 while(b>0){ 26 sum+=c[b]; 27 b-=lowbit(b); 28 } 29 return sum; 30 } 31 void add(int x,int val){ 32 while(x<=k){ 33 c[x]+=val; 34 x+=lowbit(x); 35 } 36 } 37 int main(){ 38 int a,x,y,game=0; 39 getphi(); 40 while(scanf("%d%d%d",&k,&n,&m)!=EOF){ 41 if(k==0&&n==0&&m==0)break; 42 memset(c,0,sizeof(c)); 43 for(int i=1;i<=k;i++){ 44 now[i]=m; 45 if(phi[m])add(i,1); 46 } 47 printf("CASE #%d: ",++game); 48 for(int i=0;i<n;i++){ 49 scanf("%d%d%d",&a,&x,&y); 50 switch (a){ 51 case 0:{ 52 bool b=phi[now[x]],c=phi[now[x]+y]; 53 if(b&&!c)add(x,-1); 54 if(!b&&c)add(x,1); 55 now[x]+=y; 56 break; 57 } 58 case 1:{ 59 printf("%d ",sum(y)-sum(x-1)); 60 } 61 } 62 } 63 printf(" "); 64 } 65 return 0; 66 }