题解 | #质数因子#

#include <iostream>
#include <math.h>
#include <vector>

using namespace std;

void InsertSort(vector<int>& ans, int temn);
bool isPrime(int temn, int& n);


int main() {
    int num = 0;
    int n = 0;
    vector<int> ans, tem;

    cin >> num;

    tem.push_back(num);

    while (tem.size() > 0) {
        int temn = tem.back();
        tem.pop_back();
        if (temn <= 3)
            InsertSort(ans, temn);
        else {
            if (isPrime(temn, n))
                InsertSort(ans, temn);
            else {
                tem.push_back(n);
                tem.push_back(temn / n);
            }

        }
    }

    for (int i = 0; i < ans.size() - 1; i++)
        cout << ans[i] << ' ';
    cout << ans[ans.size() - 1];

    return 0;
}

void InsertSort(vector<int>& ans, int temn) {
    if (ans.size() == 0)
        ans.push_back(temn);
    else if (temn < ans.back()) {
        int i = 0;
        ans.push_back(ans.back());
        for (i = ans.size() - 2; i > 0 && ans[i - 1] > temn; i--)
            ans[i] = ans[i - 1];
        ans[i] = temn;
    } else ans.push_back(temn);
}

bool isPrime(int temn, int& n) {
    for (int i = 2; i <= sqrt(temn); i++) {
        if (temn % i == 0) {
            n = i;
            return false;
        }

    }
    n = temn;
    return true;
}