B. T-primes【1300 / 思维 数论】

https://codeforces.com/problemset/problem/230/B
首先分析一下: 只有三个因子 例如 4 除去1和4 还有一个。我们都知道因子几乎都是一对的出现的，只有平方数是有单个的因子。
故必是一个平方数，且1-sqrt(x) 之间不准有多余的因子。说明了 sqrt(x)是一个质数。
故可以得出结论质数的平方数只有三个因子

#include<bits/stdc++.h>
using namespace std;
typedef long long LL; 
const int N=1e6+10;
int st[N],prime[N],cnt;
void init()
{
	int n=1e6;
	for(int i=2;i<=n;i++)
	{
		if(!st[i]) prime[cnt++]=i;
		for(int j=0;prime[j]<=n/i;j++)
		{
			st[i*prime[j]]=1;
			if(i%prime[j]==0) break;
		}
	}
}
bool check(LL x)
{
	if(x==1) return false;
	LL temp=sqrt(x);
	if(temp*temp==x&&!st[temp]) return true;
	return false;
}
int main(void) 
{
	init();
	int t; cin>>t;
	while(t--)
	{
		LL n; cin>>n;
		if(check(n)) puts("YES");
		else puts("NO");
	}
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37