T-primes_we know that prime numbers are positive integers t

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.

The first line contains a single positive integer, n (1 ≤ n ≤ 10000),showing how many numbers are in the array. 

The next line contains n space-separated integers xi (1 ≤ xi ≤ 10^12).

Print one line: The number of T-primes number

3
4 5 6

1

Please use long long instead of int for any Xi.

The given test has three numbers. 

The first number 4 has exactly three divisors — 1, 2 and 4. 

The second number 5 has two divisors (1 and 5), 

The third number 6 has four divisors (1, 2, 3, 6),

hence the answer for them is 1 (only the number 4 is T-primes number).

 

 

  题解：此题的意思是判断输入的数字是否有且仅有3个因数（positive divisors），并记录满足条件的输入的个数。而我们不难发现，能满足条件的数字 N 的3个因数必然是: 1、√N 、N ，且 √N 要是整数。 这个题解条件不难解决，我们只需判断：pow([sqrt(N)]，2) 是否等于 N就可以了。

然而问题又出现了，输入的数据有10^12之大，对输入的N进行循环判断必然会超时（Time Limit Exceeded）。 因此我们不得不换个思路解决问题，我们要求满足条件的输入 N，对应的 √N 是整数。换句话说就是输入的数只能是自然数的平方形式（ 即：4,9,16,25,36,49……），同时 √N 需要是素数（如4,9,25,49对应的2,3,5,7都是素数，而16,36对应的4,6不是素数），否则就会多于3个因数。（因为4*4=2*8 ，而7*7 != a*b ）。

最后就是一个小坑，要记得排除1，1并不是T-prime数。（本宝宝就被坑了）

本宝宝的码