cf230BCodeforces Round #142 (Div. 2)B_codeforce 230b

B. T-primes

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

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

Copy

3
4 5 6

output

Copy

YES
NO
NO

Note

https://codeforces.com/contest/230/problem/B

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".

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
long long t,x;
long long primes[N],cnt;
bool st[N];
void getprime(long long n)
{
    memset(st,false,sizeof st);
    st[1]=true;
    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]=true;
            if(i%primes[j]==0)
            break;
        }
    }
}
/* void getprime(long long n)//试除法也ac了
{
    memset(st,false,sizeof st);
    st[1]=true;
    for(int i=2;i<=n;i++)
    {
        if(!st[i])
        {
            primes[cnt++]=i;
        }
        for(int j=i+i;j<=n;j+=i)
        st[j]=true;
    }
}*/
int main()
{
    cin>>t;
    getprime(1e6);
    while(t--)
    {
        cin>>x;
        long long c=round(sqrt(x));//四舍五入
          if(c*c==x&&!st[c])
          cout<<"YES"<<endl;
          else  
          {
             cout<<"NO"<<endl;
          }
     }
}

题目就是要除了本身和1，开方后是质数的话，就是t-primes，借鉴了一位大佬的思路，先把1e6内的素数用线性筛找出来存素数数组内，蒟蒻的我一直用试除法一个个数去判断....才tle了，还有开方那里，数字很大，得四舍五入。