题解 | #平方因子#

#include <iostream>
using namespace std;

const int N = 1e4 + 10;
int min_prime[N];
int mp[N];

//选择埃式筛是因为可以少开一个数组，优雅一点
void get_min_prime() {
    for (int i = 2; i < N; i ++ ) {
        if (!min_prime[i]) {
            min_prime[i] = i;
            for (int j = i; j < N / i; j ++) {
                if (!min_prime[j * i]) min_prime[j * i] = i;
            }
        }
    }
}
//递推算出每个数的无平方因子部分
void get_mp() {
    mp[1] = 1;
    for (int i = 2; i < N; i ++ ) {
        mp[i] = (min_prime[i / min_prime[i]] == min_prime[i])
                ? mp[i] = mp[i / (min_prime[i] * min_prime[i])]
                : mp[i] = mp[i /min_prime[i]] * min_prime[i];
    }
}

int main() {
    get_min_prime();
    get_mp();
    int n;
    while (cin >> n) {
        if (n == 0) break;
      //无平方因子部分不等于本身说明含有平方因子
        if (mp[n] != n) cout << "Yes" << endl;
        else cout << "No" << endl;
    }
}