Codeforces 230B T-primes

http://codeforces.com/problemset/problem/230/B

3つの数で割り切れるような数であるかを判定する。
そのような数をXとおくと、Xは素数の自乗であることがわかる。
なぜなら、仮にXが素数であれば、2つの数でしか割り切れない。
だから、Xは素数でない。
素数でないから、X=a*b*c...と書けるが、
3つの数で割り切れるのだから、とりあえず、X=a*bとおく。(残り1つは1)
ここで、a,bは素数である。もし、a,bが合成数ならば、Xの約数が増える。
また、a=bである。もしそうでないならば、Xは1,a,b,a*bの4つの約数を持つ。

#include <iostream>
#include <iomanip>

#include <vector>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <bitset>
#include <numeric>
#include <algorithm>

#include <functional>
#include <cctype>

#include <complex>
#include <string>
#include <sstream>

#define pb push_back
#define all(c) c.begin(),c.end()
#define rall(c) c.rbegin(),c.rend()

#define rep(i,n) for(int i=0;i<(n);i++)
#define tr(container, it) \
    for(typeof(container.begin()) it = container.begin(); it != container.end(); ++it)
#define present(container, element) (container.find(element) != container.end())
#define cpresent(container, element) (find(all(container),element) != container.end())
#define sz(a) ((int)a.size())

typedef long long ll;
const int dx[] = {1,0,-1,0};
const int dy[] = {0,-1,0,1};
const double EPS = 1e-9;

using namespace std;

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>

using namespace std;
const long long MAX = 4000000;

bitset<MAX> isp;
void sieve(){
    bool find[MAX] = {0};
    long long i;
    for(i=2;i*i < MAX;i++){
        if(find[i]) continue;
        isp.set(i);
        for(long long j=i;j<MAX;j+=i){
            if(j%i == 0) find[j] = true;
        }
    }
    for(;i<MAX;i++){
        if(find[i]) continue;
        isp.set(i);
    }
}

int main(){
    sieve();
    int n;
    cin >> n;
    rep(i,n){
        long long x;
        cin >> x;
        double a  = sqrt(x);
        if(a != (long long)a) cout << "NO" << endl;
        else{
            if(isp[a]) cout << "YES" << endl;
            else cout << "NO" << endl;
        }
    }
    return 0;
}