题解：SP8057 AMR10C - Square Free Factorization

dsj2012 · 2024-08-26 12:42:42 · 题解

思路

首先我们要求出最多的质因子的分解个数，那么我们就可以先求出这个数的因子。
然后对于每一次的质因子我们只要这个数能被整除就除这个数然后这种质因子的个数加1。
最后我们只要输出最多的个数即可。

代码

#include<bits/stdc++.h>
using namespace std;
int T;
int work(){
    int n;
    cin >> n;
    int maxn = -1e9,ans = 0;
    for(int i = 2 ; i * i <= n ; i ++){
        ans = 0;
        while(n % i == 0){
            ans ++;
            n /= i;
        }
        maxn = max(maxn , ans);
    }
    if(n != 1){
        maxn = max(1, maxn);
    }
    return maxn;
}
int main(){
    cin >> T;
    while(T --){
        cout << work() << endl;
    }
    return 0;
}