蓝桥杯 算法提高 质数的后代

  算法提高 质数的后代  

时间限制：1.0s   内存限制：256.0MB

    

问题描述

　　在上一季里，曾提到过质数的孤独，其实从另一个角度看，无情隔膜它们的合数全是质数的后代，因为合数可以由质数相乘结合而得。
　　如果一个合数由两个质数相乘而得，那么我们就叫它是质数们的直接后代。现在，给你一系列自然数，判断它们是否是质数的直接后代。

输入格式

　　第一行一个正整数T，表示需要判断的自然数数量
　　接下来T行，每行一个要判断的自然数

输出格式

　　共T行，依次对于输入中给出的自然数，判断是否为质数的直接后代，是则输出Yes，否则输出No

样例输入

4
3
4
6
12

样例输出

No
Yes
Yes
No

数据规模和约定

　　1<=T<=20
　　2<=要判断 的自然数<=105

#include<iostream>
#include<cmath>
using namespace std;
int prime[100001];
int a[22];
int main()
{
	int n,i,j;
	cin >>n;
	for(i=0;i<=100001;i++)
	prime[i]=i;
	prime[1]=0;
	for(i=0;i<n;i++)
	cin >>a[i];
	for(i=2;i<=(100001);i++){
		if(prime[i]){
			for(j=2*i;j<=100001;j+=i){
				prime[j]=0;
			}
		}
	}
	for(i=0;i<n;i++){
		int t=a[i];
		if(prime[t])
			cout <<"No"<<endl;
		else{
			int flag=0;
			for(j=2;j<=sqrt(t);j++){
				if(prime[j]){
					if(t%j==0){
						if(prime[t/j]){
							cout <<"Yes"<<endl;
							flag=1;
							break;
						}
					}
				}
			}
			if(flag==0)
			cout <<"No"<<endl;
		}
	}
	return 0;
}