230B.md (1369B)
1 Source: https://codeforces.com/problemset/problem/230/B 2 3 B. T-primes 4 5 time limit per test 6 7 2 seconds 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 stdin 16 17 output 18 19 stdout 20 21 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. 22 23 You are given an array of *n* positive integers. For each of them determine whether it is Т-prime or not. 24 25 Input 26 27 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 *x**i* (1 ≤ *x**i* ≤ 1012). 28 29 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. 30 31 Output 32 33 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. 34 35 Examples 36 37 Input 38 39 ``` 40 3 41 4 5 6 42 ``` 43 44 Output 45 46 ``` 47 YES 48 NO 49 NO 50 ``` 51 52 Note 53 54 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".