#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
 
using namespace std;
 
// 獲取一個數的所有質因數
void primeFactors(int n, vector<int>& factors) {
    for (int i = 2; i * i <= n; ++i) {
        while (n % i == 0) {
            factors.push_back(i);
            n /= i;
        }
    }
    if (n > 1) {
        factors.push_back(n);
    }
}
 
// 遞迴生成所有可能的分解組合
void generateCombinations(const vector<int>& factors, vector<int>& current, int index, int product, int target, set<vector<int>>& results) {
    if (product == target) {
        vector<int> temp = current;
        sort(temp.begin(), temp.end()); // 排序以避免重複
        results.insert(temp);
        return;
    }
    if (product > target || index >= factors.size()) {
        return;
    }
    // 不選擇當前因數
    generateCombinations(factors, current, index + 1, product, target, results);
 
    // 選擇當前因數
    current.push_back(factors[index]);
    generateCombinations(factors, current, index, product * factors[index], target, results);
    current.pop_back();
}
 
vector<vector<int>> factorCombinations(int n) {
    vector<int> factors;
    primeFactors(n, factors);
    set<vector<int>> results;
    vector<int> current;
    generateCombinations(factors, current, 0, 1, n, results);
    return vector<vector<int>>(results.begin(), results.end());
}
 
int main() {
    int n = 12; // 你可以在這裡更改數字
    vector<vector<int>> combinations = factorCombinations(n);
 
    cout << n << " 的所有分解方式為：" << endl;
    for (const auto& combination : combinations) {
        for (int num : combination) {
            cout << num << " ";
        }
        cout << endl;
    }
    return 0;
}
 

I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8dmVjdG9yPgojaW5jbHVkZSA8c2V0PgojaW5jbHVkZSA8YWxnb3JpdGhtPgoKdXNpbmcgbmFtZXNwYWNlIHN0ZDsKCi8vIOeNsuWPluS4gOWAi+aVuOeahOaJgOacieizquWboOaVuAp2b2lkIHByaW1lRmFjdG9ycyhpbnQgbiwgdmVjdG9yPGludD4mIGZhY3RvcnMpIHsKICAgIGZvciAoaW50IGkgPSAyOyBpICogaSA8PSBuOyArK2kpIHsKICAgICAgICB3aGlsZSAobiAlIGkgPT0gMCkgewogICAgICAgICAgICBmYWN0b3JzLnB1c2hfYmFjayhpKTsKICAgICAgICAgICAgbiAvPSBpOwogICAgICAgIH0KICAgIH0KICAgIGlmIChuID4gMSkgewogICAgICAgIGZhY3RvcnMucHVzaF9iYWNrKG4pOwogICAgfQp9CgovLyDpgZ7ov7TnlJ/miJDmiYDmnInlj6/og73nmoTliIbop6PntYTlkIgKdm9pZCBnZW5lcmF0ZUNvbWJpbmF0aW9ucyhjb25zdCB2ZWN0b3I8aW50PiYgZmFjdG9ycywgdmVjdG9yPGludD4mIGN1cnJlbnQsIGludCBpbmRleCwgaW50IHByb2R1Y3QsIGludCB0YXJnZXQsIHNldDx2ZWN0b3I8aW50Pj4mIHJlc3VsdHMpIHsKICAgIGlmIChwcm9kdWN0ID09IHRhcmdldCkgewogICAgICAgIHZlY3RvcjxpbnQ+IHRlbXAgPSBjdXJyZW50OwogICAgICAgIHNvcnQodGVtcC5iZWdpbigpLCB0ZW1wLmVuZCgpKTsgLy8g5o6S5bqP5Lul6YG/5YWN6YeN6KSHCiAgICAgICAgcmVzdWx0cy5pbnNlcnQodGVtcCk7CiAgICAgICAgcmV0dXJuOwogICAgfQogICAgaWYgKHByb2R1Y3QgPiB0YXJnZXQgfHwgaW5kZXggPj0gZmFjdG9ycy5zaXplKCkpIHsKICAgICAgICByZXR1cm47CiAgICB9CiAgICAvLyDkuI3pgbjmk4fnlbbliY3lm6DmlbgKICAgIGdlbmVyYXRlQ29tYmluYXRpb25zKGZhY3RvcnMsIGN1cnJlbnQsIGluZGV4ICsgMSwgcHJvZHVjdCwgdGFyZ2V0LCByZXN1bHRzKTsKICAgIAogICAgLy8g6YG45pOH55W25YmN5Zug5pW4CiAgICBjdXJyZW50LnB1c2hfYmFjayhmYWN0b3JzW2luZGV4XSk7CiAgICBnZW5lcmF0ZUNvbWJpbmF0aW9ucyhmYWN0b3JzLCBjdXJyZW50LCBpbmRleCwgcHJvZHVjdCAqIGZhY3RvcnNbaW5kZXhdLCB0YXJnZXQsIHJlc3VsdHMpOwogICAgY3VycmVudC5wb3BfYmFjaygpOwp9Cgp2ZWN0b3I8dmVjdG9yPGludD4+IGZhY3RvckNvbWJpbmF0aW9ucyhpbnQgbikgewogICAgdmVjdG9yPGludD4gZmFjdG9yczsKICAgIHByaW1lRmFjdG9ycyhuLCBmYWN0b3JzKTsKICAgIHNldDx2ZWN0b3I8aW50Pj4gcmVzdWx0czsKICAgIHZlY3RvcjxpbnQ+IGN1cnJlbnQ7CiAgICBnZW5lcmF0ZUNvbWJpbmF0aW9ucyhmYWN0b3JzLCBjdXJyZW50LCAwLCAxLCBuLCByZXN1bHRzKTsKICAgIHJldHVybiB2ZWN0b3I8dmVjdG9yPGludD4+KHJlc3VsdHMuYmVnaW4oKSwgcmVzdWx0cy5lbmQoKSk7Cn0KCmludCBtYWluKCkgewogICAgaW50IG4gPSAxMjsgLy8g5L2g5Y+v5Lul5Zyo6YCZ6KOh5pu05pS55pW45a2XCiAgICB2ZWN0b3I8dmVjdG9yPGludD4+IGNvbWJpbmF0aW9ucyA9IGZhY3RvckNvbWJpbmF0aW9ucyhuKTsKCiAgICBjb3V0IDw8IG4gPDwgIiDnmoTmiYDmnInliIbop6PmlrnlvI/ngrrvvJoiIDw8IGVuZGw7CiAgICBmb3IgKGNvbnN0IGF1dG8mIGNvbWJpbmF0aW9uIDogY29tYmluYXRpb25zKSB7CiAgICAgICAgZm9yIChpbnQgbnVtIDogY29tYmluYXRpb24pIHsKICAgICAgICAgICAgY291dCA8PCBudW0gPDwgIiAiOwogICAgICAgIH0KICAgICAgICBjb3V0IDw8IGVuZGw7CiAgICB9CiAgICByZXR1cm4gMDsKfQo=