SGU113 Nearly prime numbers

SGU113 Nearly prime numbers
テーマの大意
N個の数を入力し、各数が2個の素数の積に等しいか否かを出力する
アルゴリズムの考え方
各数の質量因子個数が2であるかどうかを統計する
時間複雑度:O(V‾√)
コード#コード#

/** * Copyright (c) 2015 Authors. All rights reserved. * * FileName: 113.cpp * Author: Beiyu Li <[email protected]> * Date: 2015-05-22 */
#include <bits/stdc++.h>

using namespace std;

#define rep(i,n) for (int i = 0; i < (n); ++i)
#define For(i,s,t) for (int i = (s); i <= (t); ++i)
#define foreach(i,c) for (__typeof(c.begin()) i = c.begin(); i != c.end(); ++i)

typedef long long LL;
typedef pair<int, int> Pii;

const int inf = 0x3f3f3f3f;
const LL infLL = 0x3f3f3f3f3f3f3f3fLL;

const int maxv = 100000 + 5;

bool isp[maxv];
int prime[maxv], sz;
void gen_prime()
{
        sz = 0;
        memset(isp, true, sizeof(isp));
        isp[0] = isp[1] = false;
        for (int i = 2; i < maxv; ++i) {
                if (isp[i]) prime[sz++] = i;
                for (int j = 0, t; j < sz && (t = prime[j] * i) < maxv; ++j) {
                        isp[t] = false;
                        if (i % prime[j] == 0) break;
                }
        }
}

int main()
{
        gen_prime();
        int n, v;
        scanf("%d", &n);
        rep(i,n) {
                int t = 0;
                scanf("%d", &v);
                rep(j,sz) {
                        int p = prime[j];
                        if (p * p > v) break;
                        while (v % p == 0) ++t, v /= p;
                }
                if (v > 1) ++t;
                puts(t == 2? "Yes": "No");
        }

        return 0;
}