难度 1300

题目 Codeforces：

B. T-primes time limit per test 2 seconds memory limit per test 256 megabytes

　　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.

Keyword

divisors 因数

 

题目解析

本题大意是判断给出的正整数是否刚好只有三个因数。

这一题有个简单的思路就是符合题意的数字必然是一个数的平方，这样的话只要事先打表就好了。

解析完毕，以下是参考代码

 1 #include <iostream>
 2 #include <cmath>
 3 using namespace std;
 4 typedef long long ll;
 5 const int m = 1000000;
 6 int a[1000100];
 7 void primes()
 8 {
 9     a[1] = 0;
10     for (ll i = 2; i <= m; i++)a[i] = 1;
11     for (ll i = 2; i <= m; i++)
12         if (i * i <= m && a[i])
13             for (int j = i * i; j <= m; j += i)
14                 a[j] = 0;
15 }
16 int main()
17 {
18     int n; cin >> n;
19     primes();
20     while (n--)
21     {
22         ll x; cin >> x;
23         ll num = sqrt(x);
24         if (num * num == x && a[num])cout << "YES\n";
25         else cout << "NO\n";
26     }
27     return 0;
28 }