埃筛+加因数统计

对于每个数，找出其因数个数即可。可在开始时便准备一数组储存小于1e3的所有质数（其实可以在devc++中先把这些因数找出来，复制黏贴到这儿，实现o（1）访问），再对于每一个数质因数分解的同时统计个数即可，注意最后要特判是否还有大于1e3的质因数，若有，还要j将cnt+1
以下为代码：

#include<bits/stdc++.h>
using namespace std;
int n,x;
const int N=1e3+100;//1e6开根，看筛选质数到哪里
vector<int>prime;
bool mark[N];
int len;
bool sos(int x){
    
    int cnt=0;
    for(int i=0;i<len;i++){
        if(x%prime[i]==0) {
            cnt++;
            //cout<<prime[i]<<' ';
        }
        while(x%prime[i]==0){
            x/=prime[i];
        }
    }
    if(x!=1)cnt++;
    //cout<<cnt<<endl;
    if(cnt==2) return 1;
    else return 0;
}
int main(){
    ios::sync_with_stdio(false);
    cout.tie(nullptr);
    cin.tie(nullptr);
    cin>>n;
    for(int i=2;i<N;i++){
        if(!mark[i]){
            prime.push_back(i);
            for(int j=i;j<=N-i;j+=i){
                mark[j]=1;
            }
        }
    }//埃筛
    len=prime.size();
    while(n--){
        cin>>x;
        cout<<sos(x)<<endl;
    }
    return 0;
}