CF 142B Tprimes

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 thas 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 ≤ 10⁵), showing how many numbers are in the array. The next line contains n space-separated integers x_i (1 ≤ x_i ≤ 10¹²).

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 x_i is Т-prime, and "NO" (without the quotes), if it isn't.

Sample test(s)

input

3
4 5 6

output

YES
NO
NO

Note

The given test has three numbers. The first number 4 has exactly three divisors — 1, 2 and 4, thus the answer for this number is "YES". The second number 5 has two divisors (1 and 5), and the third number 6 has four divisors (1, 2, 3, 6), hence the answer for them is "NO".

 1 #include <cstdio>
 2 #include <iostream>
 3 #include <cmath>
 4 #include <cstring>
 5 using namespace std;
 6 const int MAXN = 1000000+10;
 7 long long int a[100000+10]; bool prime[MAXN];
 8 bool judge(long long int n){
 9   if (n == 1)  return false;
10   long long int x = (long long)sqrt(n);
11 //  if (x * x != n) return false;
12  // else {
13   //  if (!prime[x]) return true; 
14    // else return false;
15 //  }
16 //  printf("x = %I64d ", x);
17   if (x * x != n || prime[x]) return false; else return true;
18 }
19 int main(void){
20 #ifndef ONLINE_JUDGE
21   freopen("tprime.in", "r", stdin);
22 #endif
23   int n; memset(prime, false, sizeof(prime));
24   for (int i = 2; i * i <= MAXN; ++i)
25     if (prime[i] == false)
26       for (int j = i*2; j <= MAXN; j+=i)
27         prime[j] = true;
28   while (~scanf("%d", &n)){
29     for (int i = 0; i < n; ++i) cin >> a[i];
30     for (int i = 0; i < n; ++i)
31     {
32       if(judge(a[i])) printf("YES\n"); 
33       else
34        printf("NO\n");
35     }
36   }
37   return 0;
38 }

这题卡死了……

关键就是如何判断一个数字是不是完全平方数，方法就是先开方，转化为整型，然后再平方看是不是等于原来的数字。唉，以前做过这种的，很久不做水题了，这种东西都忘了，看来水题还是要做的……