个人笔记

#include <iostream>
#include <cmath>

using namespace std;

const int N = 1e6;
int p[N], c[N];

void work(int n) {
    int m = 0;

    for (int i = 2; i <= sqrt(n); i ++) {
        if (n % i == 0) {
            p[++ m] = i;
            c[m] = 0;

            while (n % i == 0) {
                n /= i;
                c[m] ++;
            }
        }
    }

    if (n) {
        p[++ m] = n;
        c[m] = 1;
    }

    for (int i = 1; i <= m; i ++) {
        cout << p[i] << '^' << c[i] << endl;
    }

    return;
}

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

    work(n);

    return 0;
}

时间复杂度：$O(\sqrt{n})$

原理：对于任意一个$n$，可以将其分解为$n = p_1^{c_1} \times p_2^{c_2} \times \cdots \times p_k^{c_k}$

注意$for$循环可能不会将$n$完全分解 需要再判定一次
注意输出时$i$从$1$开始 因为用的++m