一本通-1200：分解因数（递归）

【题目描述】 给出一个正整数aa，要求分解成若干个正整数的乘积，即a=a1×a2×a3×...×an，并且1<a1≤a2≤a3≤...≤an，问这样的分解的种数有多少。注意到a=a也是一种分解。

【输入】 第1行是测试数据的组数n，后面跟着n行输入。每组测试数据占1行，包括一个正整数a(1<a<32768)。

【输出】 n行，每行输出对应一个输入。输出应是一个正整数，指明满足要求的分解的种数。

【输入样例】 2 2 20

【输出样例】 1 4

---

#include <iostream>
#include <vector>
#include <iomanip>
#include <string>
#include <cmath>
#include <climits>
#include <cstdio>
#include <cstdlib>
#include <queue>
#include <stack>
#include <map>
#include <algorithm>

using namespace std;

int calculate(int n, int pre)
{
    if (n < 2 || n < pre) return 0;

    int cnt = 0;
    int limit = sqrt(n);
    for (int i = pre; i <= limit; ++i) {
        if (n % i == 0) {
            cnt += calculate(n / i, i);
        }
    }
    ++cnt; //加上自己

    return cnt;
}

int main()
{
    std::ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int caseNum; cin >> caseNum;
    while (caseNum--) {
        int n; cin >> n;
        cout << calculate(n, 2) << endl;
    }

    return 0;
}

用pre来记录上一个因数，保证现在的因数不小于上一个因数。另外因数是单增的，所以只需要考虑数字n的开根号的左半边的值。