思路：

其实就是将每个数分解质因数，只不过需要加亿点点优化：

  1. 在找到一个质因数后，要用一个循环将这个因数除干净，这样下次遇到时就不会再统计一遍，达到去重的目的。

  2. 先将 $2$ 这个特殊的质数除掉，后面从 $3$ 开始除，每次加 $2$，这样能省下挺多时间。

AC 代码：

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
#include<bits/stdc++.h>
using namespace std;
bool is_prime(int n) {
	int i;
	if(n<2)return 0;
	for(i=2; i*i<=n; i++) {
		if(n%i==0) {
			return 0;
			break;
		}
	}
	return 1;
}//判断是否为质数
int main() {
	int n,k,c=0;
	cin>>k;
	for(int i=1; i<=k; i++) {
		cin>>n;
		if(is_prime(n)){
			cout<<0<<endl;
			continue;
		}
		c=0;
		int h=2;
		if(n%h==0) {
			while(n%h==0)n/=h;
			c++;
		}
		h++;
		while(n!=1) {
			if(n%h==0) {
				while(n%h==0)n/=h;
				c++;
			}
			h+=2;
		}//分解质因数
		if(c==2) {
			cout<<1<<endl;
		}
		else cout<<0<<endl;
	}
	return 0;
}