#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e8+10;
int a[maxn];
int prime[maxn/10],cnt=0;
typedef long long int ll;
void init()
{
for(int i=2;i<=maxn;i++)
{
if(a[i]==0) prime[++cnt]=i;
for(int j=1;(ll)i*prime[j]<=maxn;j++)
{
a[i*prime[j]]=a[i]+a[prime[j]]+1;
if(i%prime[j]==0) break;
}
}
}
int main()
{
init();
int t;cin>>t;while(t--)
{
int x;cin>>x;if(a[x]<=1) cout<<"YES\n"; else cout<<"NO\n";
}
}

F Almost Prime ~Bonus Version
欧拉筛!
注意，在欧拉筛中x=p * q 被两个数筛去，如果p和q都是素数，则x标记为"殆素数"，否则不是殆素数，即第14行的内容，其余部分和普通的欧拉筛没有区别。

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e8+10;
int a[maxn];
int prime[maxn/10],cnt=0;
typedef long long int ll;
void init()
{
    for(int i=2;i<=maxn;i++)
    {
        if(a[i]==0) prime[++cnt]=i;
        for(int j=1;(ll)i*prime[j]<=maxn;j++)
        {
            a[i*prime[j]]=a[i]+a[prime[j]]+1;
            if(i%prime[j]==0) break; 
        }
    }
}
int main()
{
    init();
    int t;cin>>t;while(t--)
    {
        int x;cin>>x;if(a[x]<=1) cout<<"YES\n"; else cout<<"NO\n";
    }
}