CodeForces230B. T-primes【math 超时问题！！！】_we know that prime numbers are positive integers t

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

思路：这道题就是要找出因子只有三个的数。开始想的太简单了。超时很多很多次。。。。
首先找因子不是从2到sqrt(m) 因为如果在这其中找到一个因子（除了1和本身），那么对应的在sqrt(m)之后还有一个因子。
如果一个数只有三个因子。那么第三个因子一定是一个平方数即 temp*temp = m。
所以我们要保证的是temp是一个质数。所以这样也减少了运算规模。直接从1-n找其因子很容易超时。
今天这是感觉到C++的读入很慢。我的程序一直超时，太弱了真的。

TIP1：C++的运行速度不如C的，那么主要的原因是C++的输入输出流兼容了C的输入输出，因此，C++的速度才会变慢，如果去掉C++的输入输出的兼容性的话，速度就可C的差不多了。
ios::sync_with_stdio(false) , cin.tie(0) , cout.tie(0);
TIP2:函数调用很费时间！！！ 放在主函数里就不超时了。

#include<cstdio>  
#include<iostream>  
#include<algorithm>  
#include<cstring>  
#include<cmath>  
using namespace std;  

int main()  
{  
    ios::sync_with_stdio(false) , cin.tie(0) , cout.tie(0);
    int n,i,j;  
    long long a,b;  
    cin>>n;  
    for(i=1;i<=n;i++)  
    {  
        cin>>a;  
        b=sqrtl(a); //long double sqrtl( long double x );  用sqrt和sqrtl都是可以通过的诶
        for(j=2;j*j<=b;j++)   
        {     
            if(b%j==0)  
            {  
                break;  
            }  
        }  
        if(j*j>b && b*b==a && a>1)  
        {  
            cout<<"YES\n";  
        }  
        else  
        {  
            cout<<"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