Counting Primes

/***************************************************************************
 * #######                    #                                            *
 *    #     #    #  ######   # #    #    #   ####   #    #  #    #  #      *
 *    #     #    #  #       #   #   ##   #  #       #    #  #    #  #      *
 *    #     ######  #####  #     #  # #  #   ####   ######  #    #  #      *
 *    #     #    #  #      #######  #  # #       #  #    #  #    #  #      *
 *    #     #    #  #      #     #  #   ##  #    #  #    #  #    #  #      *
 *    #     #    #  ###### #     #  #    #   ####   #    #   ####   ###### *
 ***************************************************************************/
#include<bits/stdc++.h>
#define ll          long long
#define pb          push_back
#define endl        '\n'
#define pii         pair<ll int,ll int>
#define vi          vector<ll int>
#define all(a)      (a).begin(),(a).end()
#define F           first
#define S           second
#define sz(x)       (ll int)x.size()
#define hell        1000000007
#define rep(i,a,b)  for(ll int i=a;i<b;i++)
#define lbnd        lower_bound
#define ubnd        upper_bound
#define bs          binary_search
#define mp          make_pair
using namespace std;

#define N  10005
#define MAXN  1000005
bool prime[MAXN];
ll tree[4*N];
ll lazy[4*N]={0};
ll v[N];
void build(ll node,ll start,ll end)
{
    if(start==end)
    {
        if(prime[v[start]])
            tree[node]=1;
        else
            tree[node]=0;
        return;
    }
    ll mid=(start+end)/2;
    build(2*node,start,mid);
    build(2*node+1,mid+1,end);
    tree[node]=tree[2*node]+tree[2*node+1];
}
void update(ll node,ll start,ll end,ll l,ll r,ll val)
{
    if(lazy[node]==2)
    {
        tree[node]=(end-start+1);
        if(start!=end)
        {
            lazy[2*node]=2;
            lazy[2*node+1]=2;
        }
        lazy[node]=0;
    }
    else if(lazy[node]==1)
    {
        tree[node]=0;
        if(start!=end)
        {
            lazy[2*node]=1;
            lazy[2*node+1]=1;
        }
        lazy[node]=0;
    }
    if(start>end || l>end || r<start || r<l)
        return;
    if(start>=l && end<=r)
    {
        if(prime[val])
        {
            tree[node]=end-start+1;
            if(start!=end)
            {
                lazy[2*node]=2;
                lazy[2*node+1]=2;
            }
            lazy[node]=0;
        }
        else
        {
            tree[node]=0;
            if(start!=end)
            {
                lazy[2*node]=1;
                lazy[2*node+1]=1;
            }
            lazy[node]=0;
        }
        return;
    }
    ll mid=(start+end)/2;
    update(2*node,start,mid,l,r,val);
    update(2*node+1,mid+1,end,l,r,val);
    tree[node]=tree[2*node]+tree[2*node+1];
    return;
}
ll query(ll node,ll start,ll end,ll l,ll r)
{
    if(lazy[node]==2)
    {
        tree[node]=(end-start+1);
        if(start!=end)
        {
            lazy[2*node]=2;
            lazy[2*node+1]=2;
        }
        lazy[node]=0;
    }
    else if(lazy[node]==1)
    {
        tree[node]=0;
        if(start!=end)
        {
            lazy[2*node]=1;
            lazy[2*node+1]=1;
        }
        lazy[node]=0;
    }
    if(start>end || l>end || r<start || l>r)
        return 0;
    if(start>=l && end<=r)
    {
        return(tree[node]);
    }
    ll mid=(start+end)/2;
    ll p=query(2*node,start,mid,l,r);
    p+=query(2*node+1,mid+1,end,l,r);
    return(p);
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    ll TESTS=1,temp;
    cin>>TESTS;
    temp=TESTS;
    memset(prime, true, sizeof(prime));
    prime[1]=false;
    for (ll p=2; p*p<=MAXN; p++)
    {
        // If prime[p] is not changed, then it is a prime
        if (prime[p] == true)
        {
            // Update all multiples of p
            for (ll i=p*2; i<=MAXN; i += p)
                prime[i] = false;
        }
    }
    while(TESTS--)
    {
        cout<<"Case "<<(temp-TESTS)<<":\n";
        ll n,q,t,x,y,z;
        cin>>n>>q;
        rep(i,1,n+1)
        {
            cin>>v[i];
        }
        rep(i,0,4*n)
        lazy[i]=0;
        build(1,1,n);
        rep(i,0,q)
        {
            cin>>t;
            if(t==0)
            {
                cin>>x>>y>>z;
                update(1,1,n,x,y,z);
            }
            else
            {
                cin>>x>>y;
                cout<<query(1,1,n,x,y)<<endl;
            }
        }
    }
    return 0;
}