113. Nearly prime numbers

time limit per test: 0.25 sec / memory limit per test: 4096 KB

Nearly prime number is an integer positive number for which it is possible to find such primes P ₁ and P ₂ that given number is equal to \(P_1 * P_2\). There is given a sequence on N integer positive numbers, you are to write a program that prints “Yes” if given number is nearly prime and “No” otherwise.

Input

Input file consists of N+1 numbers. First is positive integer N (\(1 \le N \le 10\)). Next N numbers followed by N. Each number is not greater than \(10^9\). All numbers separated by whitespace(s).

Output

Write a line in output file for each number of given sequence. Write “Yes” in it if given number is nearly prime and “No” in other case.

Example(s)

Sample Input	Sample Output
1 6	Yes

---

Author	Resource	Date
: Michael R. Mirzayanov	: PhTL #1 Training Contests	: Fall 2001

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <string>
#include <sstream>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <ctime>

#define inf 0x3f3f3f3f
#define Inf 0x3FFFFFFFFFFFFFFFLL
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define Rep(i, n) for (int i = 1; i <= (n); ++i)
#define clr(x, a) memset(x, (a), sizeof x)
using namespace std;
typedef long long ll;

int main() {
  int T; scanf("%d", &T);
  while (T--) {
    int n; scanf("%d", &n);
    int cc = 0;
    for (int i = 2; i * i <= n; ++i) {
      while (n % i == 0) {
        n /= i; ++cc;
      }
      if (cc > 2) break;
    }
    if (n > 1) ++cc;
    if (cc == 2) puts("Yes");
    else puts("No");
  }
  return 0;
}