质因数分解定理

:one:

#include <iostream>
#include <vector>
using namespace std;

// 分解质因数：将x的质因数（及次数）存入factors中
void decompose(int x, vector<pair<int, int>>& factors) {
    for (int i = 2; i * i <= x; ++i) {
        if (x % i == 0) { // i是x的一个质因数
            int count = 0;
            while (x % i == 0) { // 统计i的次数
                count++;
                x /= i;
            }
            factors.emplace_back(i, count); // 存入（质因数i，次数count）
        }
    }
    if (x > 1) { // 剩余的x本身是质因数
        factors.emplace_back(x, 1);
    }
}

int main() {
    int x;
    cout << "请输入要分解质因数的正整数: ";
    cin >> x;

    vector<pair<int, int>> factors; // 动态存储质因数及其次数
    decompose(x, factors);

    // 格式化输出结果
    cout << x << "的质因数分解结果：" << endl;
    if (factors.empty() && x == 1) { // 特殊处理x=1（无质因数）
        cout << "1（没有质因数）" << endl;
    } else {
        for (size_t i = 0; i < factors.size(); ++i) {
            if (i > 0) cout << " × "; // 非第一个质因数，输出乘号
            cout << factors[i].first;
            if (factors[i].second > 1) { // 次数>1时，输出指数
                cout << "^" << factors[i].second;
            }
        }
        cout << endl;
    }

    return 0;
}