题目链接
Problem - 230B - Codeforces
一些话
找了个垃圾题解导致t了好久
别用题解代码里的输入输出，这种数据范围大的可能超时的题目直接用scanf，print，这两个是最快的
流程
读题，三个因数的数除了1和本身就只剩一个因数，此时这个因数一定是这个数的开方，因为这样才能保证是除了1和本身之外只有一个因数
看范围样例数量很多并且数字都很大，于是就对数字先进行预处理，把非素数给标记，然后对于每一次的输入用O(1)的时间来查询是否为素数。
套路
求一个数字的因数个数，判断是否为质数且样例数量多，数字范围大，
预处理：将范围内所有数据加工出来
ac代码
#include <bits/stdc++.h> using namespace std; typedef long long ll;const int maxn=1e6+5; //样例是数量很多并且数字都很大，于是就对数字先进行预处理，把非素数给标记，然后对于每一次的输入用O(1)的时间来判断是否为素数。 int a[maxn+1]; void isprime() { a[0]=a[1]=1; memset(a,0,sizeof(a)); for(int i=2;i<=maxn;i++){ if(!a[i]){ for(int j=i+i;j<=maxn;j+= i){ a[j]=1; } } } } int main(void){ int t; cin.tie(nullptr);std::ios::sync_with_stdio(false); cin >> t; ll x,y; isprime(); while(t--){ cin >> x; y = sqrt(x); if( y * y == x && x != 1 && !a[y]){ cout << "YES\n"; } else cout << "NO\n"; } return 0; }
