pokerG

HOJ 1015 Nearly prime numbers ""

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 toP1*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 consists of N+1 numbers. First is positive integer N (1<=N<=50000). 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 for each number of given sequence. Write Yes if given number is nearly prime and No in other case.

Sample Input 
1
6
Sample Output

Yes

 

  

#include <cstdio>
#include <cstdlib>
bool isPrime(int n){
	if(n == 2)
	   return true;
    if(n % 2 == 0)
       return false;
	for(int i = 3; i * i <= n; i += 2)
		if(n % i == 0)
			return false;
	return true;
}
bool isNearlyPrime(int n){
    if(n % 2 == 0 && isPrime(n / 2))
        return true;
    for(int i = 3; i * i <= n; i += 2)
        if(n % i == 0 && isPrime(i))
            if(isPrime(n / i))
              return true;
    return false;
}
int main(){
	int n;
	int a[50005];
	while(scanf("%d",&n) != EOF){
		for(int i = 0; i < n; i++)
		  scanf("%d",&a[i]);
		for(int i = 0; i < n; i++){
			if(isNearlyPrime(a[i]))
				printf("Yes\n");
			else
				printf("No\n");
		}
	}
	return 0;
}


 

blog comments powered by Disqus

Published

2013-03-27

Categories


Tags