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

胡志明t

一、算法原理与解题思路

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

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

1. #include <iostream>
   
2. #include <vector>
   
3. #include <cmath>
   
4. using namespace std;
   
5. 
   
6. // 质因数分解函数：返回质因数及其指数的向量
   
7. vector<pair<long long, int>> factorize(long long n) {
   
8.     vector<pair<long long, int>> factors;
   
9.    
   
10.     // **步：单独处理2的因子（**的偶质数）
    
11.     if (n % 2 == 0) {
    
12.         int cnt = 0;
    
13.         while (n % 2 == 0) {  // 循环除以2直到不能整除
    
14.             n /= 2;
    
15.             cnt++;  // 记录2的指数
    
16.         }
    
17.         factors.emplace_back(2, cnt);  // 保存2及其指数
    
18.     }
    
19.    
    
20.     // 第二步：处理奇数因子（从3开始，步长为2）
    
21.     for (long long i = 3; i <= sqrt(n); i += 2) {
    
22.         if (n % i == 0) {  // 检查是否能整除
    
23.             int cnt = 0;
    
24.             while (n % i == 0) {  // 循环除以当前质因数
    
25.                 n /= i;
    
26.                 cnt++;  // 记录指数
    
27.             }
    
28.             factors.emplace_back(i, cnt);  // 保存质因数及其指数
    
29.         }
    
30.     }
    
31.    
    
32.     // 第三步：处理剩余的大质数（n本身就是质数的情况）
    
33.     if (n > 1) {
    
34.         factors.emplace_back(n, 1);  // 此时n必然是个质数
    
35.     }
    
36.    
    
37.     return factors;  // 返回所有质因数及其指数
    
38. }
    
39. 
    
40. int main() {
    
41.     long long N;
    
42.     cin >> N;  // 输入待分解的数字
    
43.    
    
44.     auto factors = factorize(N);  // 获取质因数分解结果
    
45.     bool first = true;  // 标记是否是**个输出的因数
    
46.    
    
47.     // 格式化输出分解结果
    
48.     for (const auto& [prime, exp] : factors) {
    
49.         if (!first) {
    
50.             cout << " * ";  // 因数之间的连接符
    
51.         }
    
52.         first = false;
    
53.         
    
54.         cout << prime;  // 输出质因数
    
55.         if (exp > 1) {  // 如果指数大于1，输出指数形式
    
56.             cout << "^" << exp;
    
57.         }
    
58.     }
    
59.    
    
60.     cout << endl;
    
61.     return 0;
    
62. }

复制代码

三、关键算法优化点

• 单独处理2的因子：作为**的偶质数，单独处理可以提升效率
• 奇数因子检测：从3开始以步长2递增，只检查奇数
• 循环终止条件：只需检查到√n，大幅减少循环次数
• 大质数处理：**处理n>1的情况，确保不遗漏大质数
  
  

四、常见问题解答

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

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

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

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