学步园

树状数组

素数+1  非素数-1 判下 +y  前后 是否发生素数 和 非素数的转换

#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<queue>
#include<vector>
#include<cstring>
using namespace std;
typedef long long ll;
int const MAXN = 1000050;
int c[MAXN + 10],s[MAXN + 10],prime[MAXN];
int t,n,m,cnt;
int vis[MAXN];
void Get_Pirme(){
    memset(vis,0,sizeof(vis));
    cnt = 0;
    for(int i = 2;i <= sqrt(MAXN * 10);i++){
        if(!vis[i]){
            prime[cnt++] = i;
            for(int j = 2 * i;j <= sqrt(MAXN * 10);j += i){
                vis[j] = 1;
            }
        }
    }
}
bool Judge_Prime(int x){
    if(x == 1 || x == 0) return false;
    for(int i = 0;prime[i] * prime[i] <= x&&i<cnt;i++){
        if(prime[i] == x) return true;
        if(x % prime[i] == 0) return false;
    }
    return true;
}
int Lowit(int x){
    return x & (-x);
}
void Add(int x,int d){
    while(x <= t){
        c[x] += d;
        x += Lowit(x);
    }
}
int Sum(int x){
    int ret = 0;
    while(x > 0){
        ret += c[x];
        x -= Lowit(x);
    }
    return ret;
}
int main(){
    int k = 1;
    Get_Pirme();
    while(scanf("%d%d%d",&t,&n,&m),(t || n || m)){
        memset(c,0,sizeof(c));
        bool flag = false;
        if(Judge_Prime(m)) flag = true;
        for(int i = 1;i <= t;i++){
            s[i] = m;
            if(flag)Add(i,1);
        }
        printf("CASE #%d:\n",k++);
        for(int i = 0;i < n;i++){
            int x,y,z;
            scanf("%d%d%d",&z,&x,&y);
            if(z)printf("%d\n",Sum(y) - Sum(x - 1));
            else{
                int d = s[x],d1 = s[x] + y;
                s[x] += y;
                if(Judge_Prime(d) && !Judge_Prime(d1)) Add(x,-1);
                if(!Judge_Prime(d) && Judge_Prime(d1)) Add(x,1);
            }
        }

        puts("");
    }
    return 0;
}