LQ0019 数的拆分【素数】

题目来源：蓝桥杯2022初赛 C++ A组I题，C++ G组I题

题目描述
给定T个正整数a，分别问每个ai能否表示为x1^y1·x2^y2的形式。
其中x1、x2为正整数，y1、y2为大于等于2的正整数。

输入格式
输入第一行包含一个整数T，表示询问次数。
接下来T行，每行一个正整数ai。
10% 的评测用例，1 ≤ T ≤ 200，ai ≤ 10^9；
30% 的评测用例，1 ≤ T ≤ 300，ai ≤ 10^18；
60% 的评测用例，1 ≤ T ≤ 10000，ai ≤ 10^18；
100%的评测用例，1≤ T ≤ 100000，1 ≤ ai ≤ 10^18。

输出格式
对于每次询问, 如果ai 能够表示为题目描述的形式则输出yes，否则输出no。

输入样例
7
2
6
12
4
8
24
72

输出样例
no
no
no
yes
yes
no
yes

问题分析
暴力分解的方法必定会超时，参加程序代码。
有关题解原理参见参考链接。

参考链接：2022年蓝桥杯省赛 C/C++ A组题解

AC的C语言程序如下：

/* LQ0019 数的拆分 */

#include 
#include 
#include 
#include 

using namespace std;

// Eratosthenes筛选法
const int N = 4000;
bool isprime[N + 1];
int prime[N / 3], pcnt = 0;
void esieve(void)
{
    memset(isprime, true, sizeof isprime);
    prime[pcnt++] = 2;
    for (int i = 3; i <= N; i += 2)
        if (isprime[i]) {
            prime[pcnt++] = i;
            for (int j = i + i; j <= N; j += i)
                isprime[j] = false;
        }
}

typedef long long LL;

bool judge(LL n)
{
    LL t = sqrt(n);
    if (t * t == n) return true;
    t = cbrt(n);
    if (t * t * t == n) return true;
    return false;
}

int main()
{
    esieve();

    int t;
    LL a;
    scanf("%d", &t);
    while (t--) {
        scanf("%lld", &a);

        if (judge(a))
            puts("yes");
        else {
            bool flag = true;
            for (int i = 0; i < pcnt; i++) {
                int cnt = 0;
                if (a % prime[i] == 0)
                    while (a % prime[i] == 0)
                        cnt++, a /= prime[i];
                if (cnt == 1) {
                    flag = false;
                    break;
                }
            }
            puts(flag && judge(a) ? "yes" : "no");
        }
    }

    return 0;
}

超时的C语言程序（暴力）如下：

/* LQ0019 数的拆分 */

#include 

int judge(long long n)
{
    for (long long i = 2; i * i <= n; i++) {
        if (n % i == 0) {
            int cnt1 = 0;
            while (n % i == 0)
                cnt1++, n /= i;
            if (n == 1) {
                // n可以写成i^cnt1*1^2，则返回1
                if (cnt1 >= 2) return 1;
            } else {
                for (long long j = i + 1; j * j <= n; j++)
                    if (n % j == 0) {
                        int cnt2 = 0;
                        while (n % j == 0)
                            cnt2++, n /= j;
                        if (n == 1) {
                            // n可以写成i^cnt1*j^cnt2，则返回1
                            if (cnt2 >= 2) return 1;
                        }
                    }
            }
        }
    }
    return 0;
}

int main()
{
    int t;
    long long a;
    scanf("%d", &t);
    while (t--) {
        scanf("%lld", &a);

        printf("%s\n", judge(a) ? "yes" : "no");
    }

    return 0;
}