唯一分解定理（C）

#include <iostream>
#include <cmath>
using namespace std;
int pd[4010], q[4010], cnt;
void f4000(void)//4000以下的素数，线性筛
{
    for (int i = 2; i <= 4000; ++i)
    {
        if (!pd[i])
            for (int j = i * 2; j <= 4000; j += i)
                pd[j] = 1;
    }
    for (int i = 2; i <= 4000; ++i)
        if (!pd[i])
            q[++cnt] = i;
}
int pf(long long n)
{
    long long num = sqrt(n);
    while (num * num <= n)
    {
        if (num * num == n)return 1;
        ++num;
    }
    return 0;
}
int lf(long long n)
{
    long long num = pow(n, 1.0 / 3);
    while (num * num * num <= n)
    {
        if (num * num * num == n)
            return 1;
        ++num;
    }
    return 0;
}
int t, a;// t是输入数字个数，a和k是主函数用到的变量
long long shuzi[100005], k;
int main()
{
    f4000();
    scanf("%d", &t);
    for (int i = 1; i <= t; ++i)scanf("%lld", shuzi + i);
    for (int i = 1; i <= t; ++i)
    {
        int flag = 1;
        k = shuzi[i];
        if (lf(k) || pf(k))
        {
            printf("yes\n");
            continue;
        }
        for (int j = 1; j <= cnt; ++j)
        {
            a = 0;
            while (k % q[j] == 0)
            {
                k /= q[j];
                ++a;
            }
            if (a == 1)
            {
                flag = 0;
                break;
            }
        }
        if (flag && (lf(k) || pf(k)))
            printf("yes\n");
        else
            printf("no\n");
    }
    return 0;
}