题目链接|质数因子

功能:输入一个正整数，按照从小到大的顺序输出它的所有质因子（重复的也要列举）（如180的质因子为2 2 3 3 5 ）

数据范围：$1\le n\le 2\times 10^9+141\; \backslash leq\; n\; \backslash leq\; 2\; \backslash times\; 10^\{9\}+14$

方法：Pollard Rho法直接对$nn$进行质因数分解

方法一：迭代进行质因数分解

由于一个数的质因数不会超过它的算术平方根，所以我们可以枚举 $i=2i=2$到$i=\sqrt{n}i=\backslash sqrt\{n\}$。判断$nn$能否被$ii$整除，找到最小的能整除$nn$的质数，并更新$n=n\mathrm{/}in=n/i$。如果$nn$不能被$ii$整除，更新$i=i+1i=i+1$。所有合数一定至少可以分解成两个或以上的质因数，因此质因数一定早于合因数出现。最后需要检查最后这个数是否就是质数。

时间复杂度：$O(\sqrt{N})O(\backslash sqrt\{N\})$，解释：对$NN$进行质因数分解需要迭代$O(\sqrt{N})O(\backslash sqrt\{N\})$次枚举它的质因数。

空间复杂度：$O(1)O(1)$，解释：对$NN$进行质因数分解不需要额外的存储空间。

#include<iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <iostream>
using namespace std;
typedef long long ll;
int main() {
    ll num;
    cin >> num;
    for(ll i = 2; i <= sqrt(num); i++){   
    //sqrt(num)之内一定会出现第一个质因数，所有合数一定至少可以分解成两个或以上的质因数，因此质因数一定早于合因数出现。
        if(num % i == 0){
            cout << i << " ";
            num /= i;
            i -= 1;  //判断是否出现重复的质因数
        }
    }
    if(num > 1) cout << num;
    cout << "\n";
    return 0;
}

方法二：递归进行质因数分解

原理与方法一相同，但进行质因数分解的过程可以通过递归的方法实现。

时间复杂度：$O(\sqrt{N})O(\backslash sqrt\{N\})$，解释：对$NN$进行质因数分解需要递归$O(\sqrt{N})O(\backslash sqrt\{N\})$次枚举它的质因数。

空间复杂度：$O(1)O(1)$，解释：对$NN$进行质因数分解不需要额外的存储空间。

#include<iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <iostream>
using namespace std;
typedef long long ll;

void func(int num){
    int flag = 1;
    for(ll i = 2; i <= sqrt(num); i++){   //若是合数，必有一个小于sqrt(num)
        if(num % i == 0){
            flag = 0;
            num /= i;
            cout << i << " ";
            func(num);
            break;
        }
    }
    if(flag == 1) cout << num;
}

int main() {
    ll num;
    cin >> num;
    func(num);
    cout << "\n";
    return 0;
}