唯一分解定理模板

#include <bits/stdc++.h>
using namespace std;

// 质因数分解
void factorize(int n) {
    for (int i = 2; i * i <= n; i++) {
        if (n % i == 0) {
            int cnt = 0;
            while (n % i == 0) { n /= i; cnt++; }
            cout << i << "^" << cnt << " ";
        }
    }
    if (n > 1) cout << n << "^1";  // 剩下的大质因子
    cout << endl;
}

// 约数个数 = (a1+1)(a2+1)...
int countDivisors(int n) {
    int result = 1;
    for (int i = 2; i * i <= n; i++) {
        if (n % i == 0) {
            int cnt = 0;
            while (n % i == 0) { n /= i; cnt++; }
            result *= (cnt + 1);
        }
    }
    if (n > 1) result *= 2;
    return result;
}

int main() {
    factorize(360);  // 2^3 3^2 5^1
    cout << countDivisors(360) << endl;  // 24
    return 0;
}

📖 要点说明

• n = p1^a1 × p2^a2 × ...，分解唯一
• 约数个数 = (a1+1)(a2+1)...
• 最后 n>1 说明剩一个大质因子，勿遗漏

⚠️ 常见错误

• 忘处理最后剩下的大质因子
• 约数个数公式记错
• 分解时用合数试除（从2开始不会，但效率差）