sgu 113. Nearly prime numbers 素数

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 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  

#include <bits/stdc++.h> using namespace std; bool is_p(int x){ for(int i=2;i*i<=x;i++){ if(x%i==0){ return false; } } return true; } void solve(){ int n; scanf("%d",&n); while(n--){ int a; scanf("%d",&a); bool f=0; for(int i=2;i*i<=a;i++){ if(a%i==0&&is_p(i)&&is_p(a/i)){ f=1; break; } } printf("%s\n",f?"Yes":"No"); } } int main(){ solve(); return 0; }