$\operatorname{RT.}$

超级无敌水的线段树板子题，思路就是埃氏筛预处理 $10^6$ 的素数，每次修改判断修改的数是否为素数，然后区间推平为 $1$ 或 $0$，最后查询的自然就是区间和。

但是第一个点就没过。我大抵是瞎了罢，也没查出来错，望各位大佬救救我。

（lz现在去写又臭又多的化学作业了，发现错误请尽情@并嘲笑我）

#include<iostream>
#include<cstdio> 
#include<algorithm> 
#include<cstring> 
#include<cmath> 
#include<queue> 
#include<vector>
#include<cstdlib>
#include<string> 
using namespace std;  
const int N=500005;
#define int long long  
#define rd(n) n=read() 
#define ri register int
inline int read(){int ans=0,f=0;char ch=getchar();while(ch<'0'||ch>'9') f^=(ch=='-'),ch=getchar();while(ch>='0'&&ch<='9') ans=(ans<<3)+(ans<<1)+(ch^48),ch=getchar();return f?-ans:ans;}
inline void print(int n){if(n<0){putchar('-');n=-n;}if(n>9) print(n/10);putchar(n%10+'0');} 
int m,n,x,y,z; 
int v[1000050];
inline void prime(int n)
{
	memset(v,0,sizeof(v));
	v[1]=1; v[0]=1;
	for(ri i=2;i<=n;++i)
	{
		if(v[i]) continue;
		for(ri j=i;j<=n/i;++j)
		{
			v[i*j]=1;
		}
	}
}
#define lson(p) p<<1
#define rson(p) p<<1|1
struct SegmentTree{
    int l,r; 
    int sum;
    int add;
    #define l(i) t[i].l
    #define r(i) t[i].r 
    #define sum(i) t[i].sum
    #define add(i) t[i].add 
}t[N<<2];
int a[N];
inline void pushup(int p)
{
	sum(p)=sum(lson(p))+sum(rson(p));
}
inline void build(int p,int l,int r)
{
    l(p)=l;  r(p)=r;  add(p)=0;
    if(l==r) 
    {
        sum(p)=!v[a[l]];
        return;
    }
    int mid=(l+r)>>1;
    build(lson(p),l,mid); 
	build(rson(p),mid+1,r);
    pushup(p);
}
inline void spread(int p)
{  
    if(add(p)) 
    {
        sum(lson(p))=add(p)*(r(lson(p))-l(lson(p))+1); 
		sum(rson(p))=add(p)*(r(rson(p))-l(rson(p))+1); 
        add(lson(p))=add(p); add(rson(p))=add(p); 
		add(p)=0;
    }
}
inline void change(int p,int l,int r,int k)
{
    if(l<=l(p)&&r>=r(p))
    {
		sum(p)=k*(r(p)-l(p)+1);
        add(p)=k; 
        return;
    }
    spread(p);
    int mid=(l(p)+r(p))>>1;
    if(l<=mid) change(lson(p),l,r,k);
    if(r>mid) change(rson(p),l,r,k);
    pushup(p);
}  
inline int query(int p,int l,int r)
{
    if(l<=l(p)&&r>=r(p)) return sum(p);
    spread(p);
    int mid=(l(p)+r(p))>>1; 
	int ans=0;
    if(l<=mid) ans+=query(lson(p),l,r); 
    if(r>mid) ans+=query(rson(p),l,r);
    return ans;
} 
signed main(void)
{ 
	prime(1000001);
	int T=0; rd(T);
	int opt=0;
	int cnt=0;
	while(T--)
	{
		printf("Case %lld:\n",++cnt); 
	    rd(n); rd(m); 
	    for(ri i=1;i<=n;++i) rd(a[i]);
	    build(1,1,n);
		while(m--)
		{
			rd(opt);
			rd(x);
			rd(y);
			if(opt==0)
			{
				rd(z);
				change(1,x,y,!v[z]); 
			}
			else
			{
				print(query(1,x,y));
				puts("");
			}
		}
	}
    return 0;
} 
/*
1
5 3
78 2 13 12 3
1 1 2
0 4 4 5
1 1 5
*/