# 230B. T-primes （数论）

### 题意描述

We know that prime numbers are positive integers that have exactly two distinct positive divisors. Similarly, we’ll call a positive integer t Т-prime, if t has exactly three distinct positive divisors.

You are given an array of n positive integers. For each of them determine whether it is Т-prime or not.

Input The first line contains a single positive integer, n (1 ≤ n ≤ 105), showing how many numbers are in the array. The next line contains n space-separated integers xi (1 ≤ xi ≤ 1012).

Please, do not use the %lld specifier to read or write 64-bit integers in С++. It is advised to use the cin, cout streams or the %I64d specifier.

Output Print n lines: the i-th line should contain “YES” (without the quotes), if number xi is Т-prime, and “NO” (without the quotes), if it isn’t.

Examples input 3 4 5 6 output YES NO NO

### AC代码

```#include<bits/stdc++.h>
#define x first
#define y second
#pragma GCC optimize(2)
#pragma GCC optimize("Ofast")
#pragma GCC optimize(3)
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC target("sse3","sse2","sse")
#pragma GCC target("avx","sse4","sse4.1","sse4.2","ssse3")
#pragma GCC target("f16c")
#pragma GCC optimize("inline","fast-math","unroll-loops","no-stack-protector")
#pragma GCC diagnostic error "-fwhole-program"
#pragma GCC diagnostic error "-fcse-skip-blocks"
#pragma GCC diagnostic error "-funsafe-loop-optimizations"
#pragma GCC diagnostic error "-std=c++14"
#define IOS ios::sync_with_stdio(false);cin.tie(0);
using namespace std;
typedef unsigned long long ULL;
typedef pair<int,int> PII;
typedef long long LL;
const int N=5005;
const int INF=0x3f3f3f3f;
const int MOD=998244353;
int a[N];
int dp[N];
bool check(int k){
if(k<2) return true;
for(int i=2;i*i<=k;i++){
if(k%i==0) return true;
}
return false;
}
int main(){
IOS;
set<LL> ans;
for(int i=2;i<=1000000;i++){
if(!check(i)){
ans.insert((LL)i*i);
}
}
int n;cin>>n;
while(n--){
LL x;cin>>x;
if(ans.count(x)) cout<<"YES"<<endl;
else cout<<"NO"<<endl;
}
return 0;
}```

0 条评论

• ### codeforce1178B （DP）

Recall that string a is a subsequence of a string b if a can be obtained from b ...

• ### HDU 1867（kmp应用）

Generally speaking, there are a lot of problems about strings processing. Now yo...

• ### codeforce 1263C （整除分块）

这道题想了很久，打表发现了规律，每个值相同的块，最后一个因子都是n/(n/i)，但找到规律以后不知道该如何实现，看了题解以后才发现这是一道整数分块的问题。 核...

• ### HDU 5652 India and China Origins（并查集）

India and China Origins Time Limit: 2000/2000 MS (Java/Others)    Memory Limit:...

• ### HDUOJ---2642Stars（二维树状数组）

Stars Time Limit: 5000/2000 MS (Java/Others)    Memory Limit: 32768/65536 K (Jav...

• ### Codeforces 833E Caramel Clouds

E. Caramel Clouds time limit per test：3 seconds memory limit per test：256 megaby...

• ### Android打造不一样的新手引导页面（一）

版权声明：本文为博主原创文章，未经博主允许不得转载。 https://blog.csdn.net/gdutxiaoxu/article/details/...

• ### 洛谷P2863 [USACO06JAN]牛的舞会The Cow Prom

ng the other ends of her ropes (if she has any), along with the cows holding the...

• ### leetcode502. IPO

Suppose LeetCode will start its IPO soon. In order to sell a good price of its s...

• ### 翻转瓷砖Fliptile（开关反转）- POJ 3279

Farmer John knows that an intellectually satisfied cow is a happy cow who will g...