分解质因数

原理

对一个大于1的整数$n$，$n$可以分解质因数为$\prod_{i=1}^{k}p_i^{a_i} = {p_1}^{a_1}·{p_2}^{a_2}···{p_k}^{a_k}$

朴素法，循环判断每一位。

代码

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

typedef pair<int, int> pii;
vector<pii> p;

int main()
{
    int a;
    cin >> a;
    for (int i = 2; i <= a; i++) //i从2开始遍历，a每次循环都在更新
    {
        int s = 0;
        while (a % i == 0)
        {
            s++;
            a /= i;
        }
        if (s) p.push_back({i, s}); //s不为0时，加入到结果集中
    }
    for (auto u : p) cout << u.first << " " << u.second << endl;
}