减而治之

递推

#include <iostream>
#include <cmath>

using namespace std;

int main()
{
    uint32_t n;
    cin >> n;

    for (uint32_t i = 2u; i < sqrt(n) + 1; ++i) {
        while (n % i == 0) {
            cout << i << ' ';
            n /= i;
        }
    }
    if (n > 1u) {
        cout << n << ' ';
    }
    cout << endl;
}

递归

#include <cmath>
#include <iostream>
#include <string>

using namespace std;

string PrimeFactors(uint32_t i, uint32_t n)
{
    for (; i < sqrt(n) + 1; ++i) {
        if ((n % i) == 0) {
            return to_string(i) + " " + PrimeFactors(i, n / i);
        }
    }
    return to_string(n) + " ";
}

int main()
{
    uint32_t n;
    cin >> n;
    cout << PrimeFactors(2, n);
}

变更履历

2022/8/27：优化递归解法，新增递推解法