2023年GESP五级因式分解（洛谷B3871题）：质因数分解实现

一、算法原理与解题思路

质因数分解是数学中的基础算法，其核心思想是将一个正整数表示为一系列质数的乘积。本算法采用试除法实现，通过逐个测试可能的因数来分解给定的数字。

二、完整代码解析（含详细注释）

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

// 质因数分解函数：返回质因数及其指数的向量
vector<pair<long long, int>> factorize(long long n) {
    vector<pair<long long, int>> factors;
    
    // 第一步：单独处理2的因子（唯一的偶质数）
    if (n % 2 == 0) {
        int cnt = 0;
        while (n % 2 == 0) {  // 循环除以2直到不能整除
            n /= 2;
            cnt++;  // 记录2的指数
        }
        factors.emplace_back(2, cnt);  // 保存2及其指数
    }
    
    // 第二步：处理奇数因子（从3开始，步长为2）
    for (long long i = 3; i <= sqrt(n); i += 2) {
        if (n % i == 0) {  // 检查是否能整除
            int cnt = 0;
            while (n % i == 0) {  // 循环除以当前质因数
                n /= i;
                cnt++;  // 记录指数
            }
            factors.emplace_back(i, cnt);  // 保存质因数及其指数
        }
    }
    
    // 第三步：处理剩余的大质数（n本身就是质数的情况）
    if (n > 1) {
        factors.emplace_back(n, 1);  // 此时n必然是个质数
    }
    
    return factors;  // 返回所有质因数及其指数
}

int main() {
    long long N;
    cin >> N;  // 输入待分解的数字
    
    auto factors = factorize(N);  // 获取质因数分解结果
    bool first = true;  // 标记是否是第一个输出的因数
    
    // 格式化输出分解结果
    for (const auto& [prime, exp] : factors) {
        if (!first) {
            cout << " * ";  // 因数之间的连接符
        }
        first = false;
        
        cout << prime;  // 输出质因数
        if (exp > 1) {  // 如果指数大于1，输出指数形式
            cout << "^" << exp;
        }
    }
    
    cout << endl;
    return 0;
}

三、关键算法优化点

1. 单独处理2的因子：作为唯一的偶质数，单独处理可以提升效率

2. 奇数因子检测：从3开始以步长2递增，只检查奇数

3. 循环终止条件：只需检查到√n，大幅减少循环次数

4. 大质数处理：最后处理n>1的情况，确保不遗漏大质数

四、常见问题解答

Q：为什么只需要检查到√n？ A：因为如果n有大于√n的因数，那么对应的另一个因数必然小于√n，所以只需要检查到√n即可。

Q：如何处理重复的质因数？ A：通过while循环连续除以相同的因数，直到不能整除为止，并记录除法执行的次数作为指数。

Q：算法的时间复杂度是多少？ A：最坏情况下是O(√n)，但对于有大量小因数的数字效率会更高。