#include "bits/stdc++.h" using namespace std; int sushu[]={2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97}; int main(){ int n; while (cin>>n) { if (n==0) break; int flag=false; for (int i = 0; sushu[i]<= sqrt(n); ++i) { if (n%(sushu[i]*sushu[i])==0) { flag= true; break; } } if (flag) cout<<"Yes"<<endl; else cout<<"No"<<endl; } }
如果一个整数满足题目条件则它一定可以被一个质数的平方整除,假设这个数是k,k一定不超过n的根号,n最大不超过10000,所以只需要尝试100以内的素数即可