一本通-1210：因子分解

【题目描述】 输入一个数，输出其素因子分解表达式。

【输入】 输入一个整数 n (2≤n<100)。

【输出】 输出该整数的因子分解表达式。

表达式中各个素数从小到大排列。

如果该整数可以分解出因子a的b次方，当b大于1时，写做 a^b ；当b等于1时，则直接写成a。

【输入样例】 60

【输出样例】 2^2*3*5

---

#include <iostream>
#include <iomanip>
#include <vector>
#include <cmath>
#include <string>
#include <climits>
#include <cstdio>
#include <cstdlib>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <set>
#include <algorithm>

using namespace std;

void solve(int n)
{
    vector<int> num;
    for (int i = 2; i <= n; ++i) {
        while (n % i == 0) {
            num.push_back(i);
            n /= i;
        }
    }

    if (num.size() <= 1) { //本身是质数，可能size为0，比如1
        cout << n << endl; return;
    }

    map<int, int> m;
    for (size_t i = 0; i < num.size(); ++i) {
        ++m[num[i]];
    }
    //for (auto e : m) cout << e.first << " " << e.second << endl;

    map<int, int>::iterator it = m.begin();
    while (it != m.end()) {
        int digit = it -> first, cnt = it -> second;
        if (cnt == 1) cout << digit;
        else cout << digit << "^" << cnt;
        ++it;
        if (it != m.end()) cout << "*";
    }
}

int main()
{
    std::ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int n; cin >> n;
    solve(n);

    return 0;
}

注意不支持C++11，所以还是得用迭代器的写法。