题解 | #平方因子#

#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以内的素数即可