codefroces 230b B. T-primes_t-primes time limit per test2 seconds memory limit

B. T-primes
time limit per test2 seconds
memory limit per test256 megabytes
inputstandard input
outputstandard 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
inputCopy
3
4 5 6
outputCopy
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”.

题意：给你一个数n，如果这个数只有三个因子，输出YES，否则输出NO；
思路：第一次的思路是使用素因子分解，原理：任意一个正整数都能分解成若干个素数乘积的形式（自行百度），虽然这个很快，但是如果输入的是一个10的12次方的素数的话，需要判断10的6次方次，很显然会直接超时。
第二次百度题解，原来一个数只有三个因子，必然会是1和它本身，和一个素数；这个素数的平方等于它。知道了这个之后就很好做了，直接将0-10的6次方里的素数打表出来，就可以了
代码如下：

#include<bits/stdc++.h>
#define LL long long
#define Max 1001005
#define Mod 1e9+7
const LL mod=1e9+7;
const LL inf=0x3f3f3f3f;
using namespace std;
int prime[Max];
bool prim[Max];
void prim_from()//素数打表
{
    int counts=0;
    memset(prim,true,sizeof(prim));
    prim[0]=prim[1]=false;
    for(int i=2; i<=Max; i++)
    {
        if(prim[i])
            prime[counts++]=i;
        for(int j=0; j<counts; j++)
        {
            if(i*prime[j]>Max)
                break;
            prim[i*prime[j]]=false;
            if(i%prime[j]==0)
                break;
        }
    }
}
int main()
{
    int n;
    LL x;//必须用long long 不然会爆int
    prim_from();
    scanf("%d",&n);
    for(int i=0;i<n;i++){
        scanf("%lld",&x);
        double t=sqrt(x);
        int t1=sqrt(x);
       // printf("%f %d",t,t1);
        if((t-t1)<=1e-9 && prim[t1])//&&前面 确保输入来的数，开根号是一个整数 &&后面判断是否是素数
            printf("YES\n");
        else
            printf("NO\n");
    }
    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
38
39
40
41
42
43
44
45
46
47