Codeforces Round 142 (Div. 2) - B. T-primes （数论）

本文主要是介绍Codeforces Round 142 (Div. 2) - B. T-primes （数论），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

我们知道，质数是具有两个不同正除数的正整数。同样，我们把正整数 $t$ 称为质数。Т-质数，如果 $t$ 恰好有三个不同的正除数。

给你一个由 n 个正整数组成的数组。请判断其中每个整数是否为 Т-prime。

输入
第一行包含一个正整数 $n ( 1 ≤ n ≤ 10^5 )$ ，显示数组中有多少个数字。下一行包含 $n$ 个空格分隔的整数 $x_i ( 1 ≤ x_i ≤ 10^12 )$ 。
请不要使用 %lld 指定符在 С++ 中读写 64 位整数。建议使用 cin、cout 流或 %I64d指定符。

输出
打印 $n$ 行：如果数字 $x_i$ 是 Т-prime，则第 $i$ 行应包含"是"(不带引号)；如果数字 $x_i$ 不是 Т-prime，则第 $i$ 行应包含"否"(不带引号)。

虽然标签有模拟，但是这是纯纯的数论题。
首先我们知道，一个质数的因数只有1和他自己，那么一个质数的平方数的因数，就只有1和他自己还有他开平方的数。

知道了这一点就可以直接开始写出求约数个数的函数，只要按照是质数并且是一个平方数判断就可以。

代码：

#include<iostream>
#include<cmath>
using namespace std;
const int N = 1e6 + 10;int primes[N];
int cnt;
int st[N];void get_primes(){for(int i = 2;i <= N;i++){if(!st[i])primes[cnt++] = i;for(int j = 0;primes[j] <= N/i;j++){st[primes[j]*i] = 1;if(i % primes[j] == 0)break;}}
}int main(){get_primes();int n;cin >> n;while(n--){long long a;cin >> a;long long t = (long long)sqrt(a);//这里要判断t*t是否等于a，因为sqrt得来的t有可能不是a的开根if( !st[t] && t*t == a && t > 1)cout << "YES\n";else cout << "NO\n";}return 0;
}