参考程序（线性筛法）
#include <iostream>
#include <vector>
using namespace std;const int MAXN = 10000001; // 最大数字范围// 保存每个数的质因子数量
vector<int> primeFactors(MAXN, 0);void linearSieve() {// 从 2 开始筛选for (int i = 2; i < MAXN; i++) {// 如果 i 是质数if (primeFactors[i] == 0) {// 质数的质因子数是 1（它自己）primeFactors[i] = 1;// 从 i 的倍数开始更新质因子数量for (int j = i * 2; j < MAXN; j += i) {primeFactors[j]++;}}}
}int main() {int t;cin >> t;// 预处理质因子数量linearSieve();while (t--) {int n;cin >> n;// 判断该数字是否是幸运数字if (primeFactors[n] == 2) {cout << "1\n";} else {cout << "0\n";}}return 0;
}参考程序（因数分解法）
#include<bits/stdc++.h>
using namespace std;
map<int,int> mp;
const int N = 1e5+10;
int calc(int x)
{int res = 0;set<int> s;for (int i = 2; i * i <= x; i++) {if (x % i == 0) {s.insert(i);while (x% i == 0){x/= i;}}}if (x != 1) {s.insert(x);}return (int)s.size();
}
int a[N];
int main()
{int n;cin>>n;long long ans = 0;int pre = 0;for(int i=1;i<=n;i++){cin>>a[i];int x = calc(a[i]);if(x==2)cout<<"1\n";else cout<<"0\n";}
}
