Nearly prime numbers

Problem Description

Nearly prime number is an integer positive number for which it is possible to find such primes P1 and P2 that given number is equal to P1*P2. 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£N£10). Next N numbers followed by N. Each number is not greater than 109. 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.

Sample Input

1
6

Sample Output

Yes

Solution

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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#include <bits/stdc++.h>

bool checkPrime(int num) {
for(int i = 2; i <= std::sqrt(num) + 1; i++) {
if(num % i == 0) {
return false;
}
}
return true;
}

int main() {
std::ios::sync_with_stdio(false);
long long maxn = std::sqrt(1e10);
std::vector<bool> visit = std::vector<bool>(maxn, false);
std::vector<int> prime{};

for(unsigned int i = 2; i < visit.size(); i++) {
if(visit[i] == true) {
continue;
}
prime.push_back(i);
for(unsigned long j = i * 2; j < visit.size(); j += i) {
visit[j] = true;
}
}

int n;
std::cin >> n;
while(n--) {
int num;
std::cin >> num;
bool flag = false;
for(const auto& primeNum : prime) {
if(primeNum >= num) {
continue;
}
if(num % primeNum != 0) {
continue;
}
int quotient = num / primeNum;
if(quotient > prime.back()) {
if(checkPrime(quotient) == true) {
flag = true;
break;
}
} else {
auto res = std::lower_bound(prime.begin(), prime.end(), num / primeNum);
if(res != prime.end() && *res * primeNum == num) {
flag = true;
break;
}
}
}
std::cout << (flag ? "Yes" : "No") << std::endl;
}
return 0;
}