1565: 蓝桥杯算法提高VIP-质数的后代

解题思路:

使用的是算数基本定理，一个数只能被唯一分解成多个质数的乘积，这样不需要构造质数表了。

最好情况下在log n的时间复杂度，用k表示分解出了几个质数，如果k！=2的话就打印no

参考代码:

#include <stdio.h>
#include <math.h>

int main ()
{
	int i,k=0;
	int n,z=0;
	scanf("%d",&z);
	while(z--){
		scanf("%d",&n);
		for(i=2;i<=n;i++){
			while(n%i==0){
				n/=i;
				k++;
			}
		}
		if(k!=2){
			printf("No\n");
		}else{
			printf("Yes\n");
		}
		k=0;
	} 
	
	return 0;
}