写在前面

本来我还是在开开心心的写题，这个题找到并证明贪心还是花了不少时间的，AC后看了下别人的代码，和我第一次的思路相似，代码就差了一点点，那一瞬间，我突然明白，原来这就是被打击的感觉。
没心情写题了，看了好多题解都没有比较好的解释，我就打算自己写一下题解，顺便给出这样贪心的理由。

正文

看到题目，数据很大（n最大为10^9，所以要考虑复杂度低于O(n)的算法）
我们可以参考求一个数字质因数个数的方法：

//A为目标数字
int res = 0;
for (int i = 2; i * i <= A; i++) {
    while (A % i == 0) {
        A /= i;
        res++;
    }
}
if (A > 1) res++;

这一题要求拆分的结果不能有重复数字，那么重复的质因数去哪儿了？与其他质因数相乘变成了合数。所以我们就按照求质因数的思路，把循环中的while改成if，这样相当于每次都找到一个质因数，但是这个质因数并不一定包含于最终结果的集合，可能在一遍循环之后，n并没有如愿的变成1（有些情况下因数大于sqrt(n)，有些情况下i大于当前的n且n没能变为1），所以我们要分别考虑这两种情况，对第一种情况，这种因数只会出现一次，所以在循环结束后将res + 1即可，对于第二种情况，这个n一定不能作为新的质因数产生了，因为如果它是一个新的质因数，那么i在循环到该值时会产生对应的质因数，所以它只能与其他数一起产生一个合数。
以上所述的n都是动态的，第一种情况的判断见代码：

#include <iostream>
#include <cmath>
using namespace std;

int main() {
    int T;
    cin >> T;
    while (T--) {
        int n;
        scanf("%d", &n);
        int res = 0;
        int i;
        for (i = 1; i * i <= n; i++) {
            if (n % i == 0) {
                res++;
                n /= i;
            }
        }
        i--;
        if (i < n) res++;
        printf("%d\n", res);
    }
    return 0;
}

其他

看到很多人都喜欢无脑的用long long，我并不是不推荐，但是我觉得做题应该要清楚什么时候要用int，什么时候需要long long，只要保证正确，能用int我就绝不用long long，要培养这方面的敏感，以防以后栽倒这个坑里。