题目分析

1. 题目给出我们一个数字
2. 我们要找出这个数字的质数因子，包括重复的质数因子

方法一：递归

• 实现思路
  • 我们规定递归函数的定义为
    • 本轮应该处理的数字为n，选定的因子为i，题目输入数据为num
    • 递归函数退出的条件为选定的因子i的平方大于num，则说明我们已经基本逼近到了num的最大因子（因为剩余的质因子是可能剩一个或者全部找完了）
    • 判断当前i是否为n的因子，如果是n的因子，则n更新为n/i，i值不变并进入下一轮的寻找
    • 当前i如果不是n的因子，则需要更新i的值，继续递归寻找
  • 递归结束之后，还需要判断n是否已经除尽所有的因子，如果n此时不是1，则说明最后一个质因子是n本身，并且n是大于i的，所以在递归里面没有找到

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

// 递归函数三个参数分别表示：
// 1. 每一轮都除以我们选定的因子i，来更新n值，进入下一轮的运算
// 2. i表示我们不断从2开始选择所有的因子，因为我们每轮都将包含多少i因子就全部处理干净，因此在后面有些非质数遍历到的时候也不会受影响
// 3. 从输入中读取的值
void f(int& n, int i, int num) {
    if(i * i > num) return;            // 递归退出：因子找到输入的数字开根号值为止就不在继续找下去
    if(!(n % i)) {                     // 判断如果i是当前n的因子
        cout << i << " ";              // 输出i
        n /= i;                        // 迭代n的值
        f(n, i, num);                  // 下一轮继续判断是否有i因子仍旧存在
    }
    else {
        f(n, i + 1, num);              // 否则下一轮递归迭代i值，找下一个因子
    }
}

int main() {
    int n;
    cin >> n;
    f(n, 2, n);                        // 递归调用
    if(n != 1) cout << n << " ";       // 最终判断
    return 0;
}

复杂度分析

• 时间复杂度：$O(n)O(n)$，时间复杂度和n的大小有关，因为是迭代i值进行不断寻找的过程
• 空间复杂度：$O(n)O(n)$，递归栈空间的代价同样和i有关，i是迭代的所以也是和n相关的

方法二：迭代

• 实现思路
  • 我们通过遍历因子i来尝试是否是n的因子
  • 如果能i是n的因子，则更新$n=n\mathrm{/}in=n/i$，并继续循环寻找
  • 直到找到$i^2>ni^2>n$的收为止，并最后检查是否有大于i的因子剩下来
  • 输出所有的因子即可

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    int n;
    while(cin >> n) {
        for(int i = 2; i * i <= n; i++) {    // 从质因数2开始遍历
            while(!(n % i)) {                // 看看有没有多个重复的因子
                n /= i;
                cout<< i << " ";
            }
        }        
        if(n != 1) {                         // 检查是否有剩余的，比数字本身开根号后大的质因子
            cout << n << " ";
        }
    }
    return 0;
}

复杂度分析

• 时间复杂度：$O(n)O(n)$，时间复杂度和n的大小有关，因为是迭代i值进行不断寻找的过程
• 空间复杂度：$O(1)O(1)$，没有借助额外的线性空间