1015.cpp

这是哈尔滨工业大学acmOJ的源代码

/*  This Code is Submitted by wywcgs for Problem 1015 on 2006-02-08 at 15:50:15 */ 
#include <cstdio>

const int MAX = 32000;

int main()
{
	bool prime[MAX] = { true, true };
	int n, i, j, t, T;
	int p[4000], pn = 0;
	
	for(i = 2; i < MAX; i++)
		if(!prime[i]) {
			p[pn++] = i;
			for(j = 2; i*j < MAX; j++) prime[i*j] = true;
		}
	scanf("%d", &T);
	for(t = 0; t < T; t++) {
		scanf("%d", &n);
		int fn = 0;
		for(i = 0; i < pn && fn <= 2 && n != 1; i++)
			while(n % p[i] == 0) n /= p[i], fn++;
		printf("%s\n", ((fn == 2 && n == 1) || (fn == 1 && n != 1)) ? "Yes" : "No");
	}
	
	return 0;
}