链接：https://ac.nowcoder.com/acm/contest/115184/L
题目要求：
故障机器人探索完尖塔后得到了 n 个遗物，其中第 i 个遗物的价值是 ai。如果一个遗物的价值的因数个数是质数且不等于 2，那么故障机器人就认为这个遗物是一个完美遗物。故障机器人想要知道其拥有的完美遗物的价值之和是多少。
输入要求：
第一行，输入一个整数 n （1≤n≤2⋅105），表示故障机器人所拥有遗物的数量。
第二行，输入 n 个整数 a1,a2,…,an（1≤ai≤1012），其中 ai 表示故障机器人第 i 个遗物的价值。
输出要求：
一行，一个整数，表示故障机器人所拥有的完美遗物的价值之和。
思路分析：
判断当前遗物是否为完美遗物需三个步骤：
1、计算该遗物价值的因数个数t；2、t为质数；3、t≠2。
①我们需要计算一个数的因数的个数，
数论里的一个基本结论：一个正整数 n 分解成素因数乘积后：
n=p1a1⋅p2a2⋅⋯⋅pk^ak
那么它的因子个数是：d(n)=(a1+1)(a2+1)⋯(ak+1)因为 ai+1≥2，每一项 ≥2，并且至少有两项（k≥2）时，这个乘积一定不是质数。只有当 n 是形如 p^q 的数（即只有一个素因子）时，才可能让 d(n)=q+1 是质数。所以为了使 d(n) 是质数，n 必须是**某个质数 p 的 q 次幂（n=p^q）**，而且 q+1 也必须是质数（因为 d(n)=q+1）。因此我们可以直接通过枚举，将所有符合条件的完美遗产数标记为真。
②在此之前，我们需要写一个素数筛，对数组进行预处理方便后续的判断直接使用。
在此我用的是经典的埃拉托色尼筛法。
#include <iostream>
#include <vector>
#include <cmath>
#define int long longusing namespace std;const int N = 1e6;vector<bool> is_prim;
vector<int> get_prim(int n){is_prim.assign(n+1, true);is_prim[0]=is_prim[1]=false;vector<int> prim;for(int i=2;i<n;i++){if(is_prim[i]){prim.push_back(i);for(int j=i*2;j<=n;j+=i){is_prim[j]= false;}}}return prim;
}
signed main() {int n;cin >> n;vector<int> prim= get_prim(N);vector<bool> judge(N+1, false);for(auto p:prim){int i=2;int x=p*p;while(x<N*N){if(i+1<is_prim.size()&&is_prim[i+1]){int q= sqrtl(x);if(q*q==x) judge[q]=true;}i++;x*=p;}}int numb,ans=0;for(int i=0;i<n;i++){cin>>numb;int m= sqrtl(numb);if(m*m==numb&&judge[m]){ans+=numb;}}cout<<ans<<endl;return 0;
}