唯一分解定理，也被称为算术基本定理，是数论中的一个核心定理。在 C++ 编程里，它能在诸多场景发挥作用，像计算最大公约数、最小公倍数、约数个数等。下面会从定理内容、证明思路、C++ 实现、复杂度分析以及应用场景等方面进行详细总结。

定理内容
任一大于 1 的自然数 (N) 都可以唯一地分解成有限个质数的乘积，即：
N = p1^a1 p2^a2.…pk^ak
其中 p1<p2<… <pk为质数，a1,a2,…,ak 为正整数。这里的 “唯一” 指的是，除了质因数的排列顺序外，分解形式是唯一的。
证明思路
存在性：采用数学归纳法。对于N = 2，2本身就是质数，分解形式为2¹，存在性成立。假设对于所有小于 N的自然数，都能分解成质数的乘积。若 N 是质数，那么分解形式就是 N¹；若N是合数，设 N = a x b（1 < a,b < N），由归纳假设可知，a 和 b 都能分解成质数的乘积，所以 N 也能分解成质数的乘积。
唯一性：假设存在两种不同的质因数分解形式 N = p1^a1}p2^a2…pk^ak = q1^b1q2^b2…qm^bm，根据质数的性质逐步推导，可得出这两种分解形式实际上是相同的（除了质因数的排列顺序）。

C++ 实现
分解质因数

#include <iostream>
#include <vector>
#include <unordered_map>

// 分解质因数
std::unordered_map<int, int> primeFactorization(int n) {
    std::unordered_map<int, int> factors;
    for (int i = 2; i * i <= n; ++i) {
        while (n % i == 0) {
            factors[i]++;
            n /= i;
        }
    }
    if (n > 1) {
        factors[n] = 1;
    }
    return factors;
}

int main() {
    int num = 84;
    std::unordered_map<int, int> factors = primeFactorization(num);
    std::cout << num << " = ";
    bool first = true;
    for (const auto& factor : factors) {
        if (!first) {
            std::cout << " * ";
        }
        std::cout << factor.first;
        if (factor.second > 1) {
            std::cout << "^" << factor.second;
        }
        first = false;
    }
    std::cout << std::endl;
    return 0;
}

复杂度分析

• 时间复杂度：分解质因数的时间复杂度为 (O(\sqrt{n}))，这是因为只需要检查到 (\sqrt{n}) 即可。
• 空间复杂度：(O(k))，其中 (k) 是质因数的个数。

应用场景

计算最大公约数和最小公倍数
若 A = p1^a1p2^a2…pk^ak，B = p1^b1p2^b2… pk^^bk（允许某些指数为 0），则：

• 最大公约数 gcd(A,B)=p1^min(a1,b1)p_{2}^min(a2,b2)… pk^min(ak,bk)
• 最小公倍数 lcm (A,B)=p1^max(a,b)p2^max(a1,b1)… pk^max(ak,bk)

#include <iostream>
#include <unordered_map>
#include <algorithm>

// 分解质因数
std::unordered_map<int, int> primeFactorization(int n) {
    std::unordered_map<int, int> factors;
    for (int i = 2; i * i <= n; ++i) {
        while (n % i == 0) {
            factors[i]++;
            n /= i;
        }
    }
    if (n > 1) {
        factors[n] = 1;
    }
    return factors;
}

// 计算最大公约数
int gcd(int a, int b) {
    auto factorsA = primeFactorization(a);
    auto factorsB = primeFactorization(b);
    int result = 1;
    for (const auto& factor : factorsA) {
        if (factorsB.find(factor.first) != factorsB.end()) {
            result *= std::pow(factor.first, std::min(factor.second, factorsB[factor.first]));
        }
    }
    return result;
}

// 计算最小公倍数
int lcm(int a, int b) {
    return a / gcd(a, b) * b;
}

int main() {
    int a = 24;
    int b = 36;
    std::cout << "GCD of " << a << " and " << b << " is: " << gcd(a, b) << std::endl;
    std::cout << "LCM of " << a << " and " << b << " is: " << lcm(a, b) << std::endl;
    return 0;
}

计算约数个数
若 N = p1^a1p2^a2 …pk^ak，则 N 的约数个数为 (a1+ 1)(a2 + 1) … (ak + 1)。

#include <iostream>
#include <unordered_map>

// 分解质因数
std::unordered_map<int, int> primeFactorization(int n) {
    std::unordered_map<int, int> factors;
    for (int i = 2; i * i <= n; ++i) {
        while (n % i == 0) {
            factors[i]++;
            n /= i;
        }
    }
    if (n > 1) {
        factors[n] = 1;
    }
    return factors;
}

// 计算约数个数
int countDivisors(int n) {
    auto factors = primeFactorization(n);
    int divisors = 1;
    for (const auto& factor : factors) {
        divisors *= (factor.second + 1);
    }
    return divisors;
}

int main() {
    int num = 24;
    std::cout << "Number of divisors of " << num << " is: " << countDivisors(num) << std::endl;
    return 0;
}

总结
唯一分解定理是数论的基石之一，在 C++ 编程中，通过对自然数进行质因数分解，可以高效地解决许多与数论相关的问题，如计算最大公约数、最小公倍数、约数个数等。分解质因数的时间复杂度为 O(sqrt{n})，在实际应用中，根据具体问题合理运用该定理能显著提升算法效率。