纯暴力不加卡时直接草过去了

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn=1e6+7;
int N,Q;
int prime[78888],cnt_prime;
bool book[maxn];
void xxs(){
	book[1]=true;
	for(int i=2;i<=1000000;i++){
		if(!book[i])prime[++cnt_prime]=i;
		for(int j=1;j<=cnt_prime&&i*prime[j]<=1000000;j++){
			book[i*prime[j]]=true;
			if(i%prime[j]==0)break;
		}
	}
}
int cnt[maxn];
int main(){
	xxs();
	scanf("%d %d",&N,&Q);
	while(Q--){
		char op;scanf(" %c",&op);
		if(op=='S'){
			int xx;scanf("%d",&xx);
			if(xx==1)continue;
			cnt[xx]^=1;
		}else if(op=='C'){
			int l,r;scanf("%d %d",&l,&r);
			bool flag=0;
			for(int i=1;i<=cnt_prime;i++){
				if(prime[i]>r)continue;
				int tot=0;
				for(int j=l/prime[i]*prime[i];j<=r;j+=prime[i]){
					if(j<l)continue;
					if(cnt[j])++tot;
					if(tot>=2){flag=1;break;}
				}
				if(flag)break;
			}
			if(flag)puts("DA");
			else puts("NE");
		}
	}
	return 0;
}