题目背景

对应的选择、判断题：试题 - GESP 202406 C++ 五级 - 洛谷有题

题目描述

小杨认为他的幸运数字应该恰好有两种不同的质因子，例如，12=2×2×3 的质因子有 2,3，恰好为两种不同的质因子，因此 12 是幸运数字，而 30=2×3×5 的质因子有 2,3,5，不符合要求，不为幸运数字。

小杨现在有 n 个正整数，他想知道每个正整数是否是他的幸运数字。

输入格式

第一行包含一个正整数 n，代表正整数个数。

之后 n 行，每行一个正整数。

输出格式

输出 n 行，对于每个正整数，如果是幸运数字，输出 1，否则输出 0。

输入输出样例

输入 #1复制

3
7
12
30

输出 #1复制

0
1
0

说明/提示

样例解释

7 的质因子有 7，只有一种。

12 的质因子有 2,3，恰好有两种。

30 的质因子有 2,3,5，有三种。

数据范围

对于全部数据，保证有 1≤n≤104，每个正整数 ai​ 满足 2≤ai​≤106。

代码实现：

#include <iostream>
#include <vector>
using namespace std;
const int MAX = 1000000;
vector<int> minp(MAX + 1);

void init()
{
    for (int i = 2; i <= MAX; i++)
    {
        if (!minp[i])
        {
            minp[i] = i;
            for (long long j = 1LL * i * i; j <= MAX; j += i)
                if (!minp[j]) minp[j] = i;
        }
    }
}

int count_factor(int x)
{
    int cnt = 0;
    while (x > 1)
    {
        int p = minp[x];
        cnt++;
        while (x % p == 0) x /= p;
    }
    return cnt;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    init();
    int n;
    cin >> n;
    while (n--)
    {
        int x;
        cin >> x;
        if (count_factor(x) == 2) cout << "1\n";
        else cout << "0\n";
    }
    return 0;
}