# SGU 113 - Nearly prime numbers

## Description

Nearly prime number is an integer positive number for which it is possible to find such primes $P_1$ and $P_2$ that given number is equal to $P_1\cdot 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\leq N\leq 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.

## Sample Input

 1 2  1 6 

## Sample Output

 1  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  #include #include #include #include #include using namespace std; const int MAX = 32000; bool pPrimes[MAX]; vector pVec; int main() { unsigned long long N, x, y; memset(pPrimes, true, sizeof(pPrimes)); for(int i = 2; i < MAX; i++) { if(pPrimes[i]) { pVec.push_back(i); for(int j = i + i; j < MAX; j += i) { pPrimes[j] = false; } } } cin >> N; for(int i = 1; i <= N; i++) { cin >> x; bool bFlag = false; for(int j = 0; j < pVec.size(); j++) { if(x % pVec[j] == 0) { y = x / pVec[j]; bool bTmp = true; for(int k = 2; k * k <= y; k++) { if(y % k == 0) { bTmp = false; break; } } if(y <= 1) { bTmp = false; } if(y == 2) { bTmp = true; } if(bTmp) { bFlag = true; break; } } } if(bFlag) { cout << "Yes" << endl; } else { cout << "No" << endl; } } return 0; }