思路

Jerry是一家公司销售部门的经理。这家公司有很多连锁店，编号为1，2，3，… Jerry每天必须关注每家连锁店的商品数量及其变化，一项很乏味的工作。在连锁店比较少的时候，Jerry喜欢计算编号在[i,j]区间内的连锁店中商品数量为素数的有多少家，但是现在连锁店的数量急剧增长，计算量很大，Jerry很难得出结果

思路

zhxisshy
就是用树状数组
一个数组a来表示这个店的值是多少，每次判断加上一个数后是否为为素数，用树状数组存储素数的个数就可以了

#include 
#include 
#include 
#include 
using namespace std;
#define maxn 1500005
#define fill(x, y) memset(x, y, sizeof(x))
int a[maxn], t[maxn];
int n, m, c;
int check(int x)
{
        if (x == 0 || x == 1) return false; 
    for (int i = 2; i <= sqrt(x); i++)  
    {  
        if(x % i == 0)  
            return false;  
    }  
    return true; 
}
int add(int p, int x)
{
        while (p <= n)
        {
                t[p] += x;
                p += p & (-p);
        }
        return 0;
}
int count(int p)
{
        int ans = 0;
        while (p > 0)
        {
                ans += t[p];
                p -= p & (-p);
        }
        return ans;
}
int main()
{
        int tt = 0;
        while (scanf("%d%d%d", &n, &m, &c) , n != 0 || m != 0 || c != 0)
        {
                fill(t, 0);
                tt++;
                printf("CASE #%d:\n", tt);
                int yy = check(c);
                for (int i = 1; i <= n; i++)
                {
                        a[i] = c;
                        if (yy == 1) add(i, 1);
                }
                for (int i = 1; i <= m ; i++)
                {
                        int z, x, y;
                        scanf("%d%d%d", &z, &x, &y);
                        if (z == 0)
                        {
                                int fl = a[x];
                                a[x] += y;
                                int l = check(fl), r = check(a[x]);
                                if (r == 1 && l == 0) add(x, 1);
                                else if (r == 0 && l == 1) add(x, -1);
                        }
                        else
                        {
                                printf("%d\n", count(y) - count(x - 1));
                        }
                }
                printf("\n");
        }
}