题解 | #质数因子#

// 递归解法

#include<iostream>
#include <math.h>
#include<vector>
#include<algorithm>
using namespace std;

vector<int> prime_vec;
int prime(int num)
{
    int i=sqrt(num);
    while(i>1)
    {
        if (num%i==0){   
            prime(i);
            prime(num/i);
            break; // mark 找到一组分解 就退出
        }
        i--; //mark 不是在if的else里
    }
    if (i==1)
        prime_vec.push_back(num);
    return 0;
}

int main()
{
    int num;
    cin>>num;
    
    prime(num);
    std::sort(prime_vec.begin(),prime_vec.end());
    
    for (const auto &v:prime_vec)
        cout<<v<<" ";
    cout<<endl;
    
    return 0;
    
}