题目

题目描述：
在遥远的米♂奇♂妙♂妙♂屋里住着一群自然数，他们没事就喜欢拆♂开自己来探♂究。
现在他们想知道自己最多能被拆分成多少个不同的自然数，使得这些自然数相乘的值等于被拆分的数。

输入描述：
第1行输入一个整数T，代表有T组数据。
第2-T+1行，每行输入一个整数n，代表需要被拆分的数。
数据保证：0<T≤100，0<n≤109。

输出描述：
输出一共T行，第i行输出一个整数，代表第i行输入的n最多可以被拆分成多少个不同的自然数。

解析

这道题其实不是很难，但是我为啥要写呢？因为我被自己坑了一下下。

  • 首先要分成最多的自然数，自然而然的就会想到：拆分素因子。

素数筛：
  1. 我们一般的素数筛，就是一个一个把素因子拿掉： 
    for (int i = 1; i * i < n; i++)
        while (0 == n % i) {
                //do
        n /= i;
    }
if  (n  >  1)  //do;
  2. 但是这道题告诉我们因子不能重复，而且相乘还要为原来的数。我们自然而然的就想到了： 
    if (0 == n % i) {
        //do
    n /= i;
}
  3. 当然，这一点问题都没有，你想的没错！但你也许不知道这样为什么就对了。下面我就告诉你这个操作是什么意义。
  4. 我们从小到大筛选出每一个素因子，还有素因子之积（因为素因子只能选一个，自然就会在挑选的时候结合）。
    栗子：我们假如因子有两个2，三个3，那我们在选完一个2，一个3之后，我们后面是不是自然而然的选6。因为因子没有用完嘛。
  5. ————————————————————分ger线————————————————————
  6. 然后我们的一般素数筛中，最后是有可能遗漏一个数没有除的，在这道题里面也是非常特殊的一个点。
    一般素数筛栗子：假如就是12这个数字，我们会先将两个2筛掉，然后n就变成了3对吧。这里我们就不满足i * i <= n了，所以出去还要来一个n > 1的特判，防止漏掉一个数。
  7. 但是这道题呢？我们的每个素因子是可能筛不完的，自然就有可能到了最后依旧还有因子残留，如果像上面那样筛的话，可能就会多出一个因子了。
    栗子：这回我们用18，18就是2,3,3对吧，我们筛掉2后，n=9，按照i * i <= n，我们筛出了一个3来，但这个时候还有个3，是不是就进了n > 1的特判？
    所以我们就要注意了：最后可能有因子无法使用的判断，那多的咋办呢？很简单，我们直接不要他就行了嘛，就把他乘进最后一个因子里面，就会出来2和9了。
    那怎么做呢？我们就变成i * i < n就行了，因为特判就是在最后一个因子重复的时候存在的。

操作：
  • 所以这道题，按照上面的讲解，就可以简单的得到： 
    for (int i = 1; i * i < n; i++)
    if (0 == n % i) {
            ans++;
        n /= i;
        }
ans++;//最后一个残留的因子，因为改成<号一定会漏出来

打代码哈：
  1. 输入变量。
  2. 变式因子筛。
  3. 看我代码哈~

AC代码 

#include <iostream> 
using namespace std; 
#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); 
//代码预处理区

int main() {
    IOS;
    int T; cin >> T;
    while (T--) {
        int n; cin >> n;
        int ans = 0;
        for (int i = 1; i * i < n; i++)
            if (0 == n % i) {
                ans++;
                n /= i;
            }
        cout << ans + 1 << endl;
    }
    return 0; 
}
//函数区