Phân tích N ra thừa số nguyên tố

Bài toán: Cho một số nguyên dương \(n\), hãy phân tích \(n\) ra thừa số nguyên tố

Input: Gồm một dòng duy nhất là số nguyên dương \(n \ (1 \le n \le 10^{12})\).

Output: Gồm \(m\) dòng, mỗi dòng in ra 2 số \(x, y\) cách nhau một dấu cách được sắp xếp theo thứ tự tăng dần của \(x\) với \(m\) là số lượng thừa số nguyên tố của \(n, x\) là thừa số nguyên tố của \(n\) và \(y\) là số mũ của \(x\).

Ví dụ:

input

output

1
2
3

Ý tưởng

Để phân tích \(n\) ra thừa số nguyên tố ta chia \(n\) cho ước nguyên tố nhỏ nhất của \(n\) và cứ lặp lại bước đó cho đến khi \(n = 1\).
Ví dụ:

code

#include <bits/stdc++.h>

using namespace std;

vector<pair<long long,int>> factorize(long long n) {
    vector<pair<long long, int>> fac;
    for (long long i = 2; i*i <= n; ++i) {
        if (n % i == 0) {
            fac.emplace_back(i, 0);
            while (n % i == 0) {
                fac.back().second++;
                n /= i;
            }
        }
    }
    if (n > 1) fac.emplace_back(n, 1);
    return fac;
}

int main() {
    long long n; cin >> n;
    auto fac = factorize(n);
    for (auto f : fac) cout << f.first << ' ' << f.second << '\n';
    return 0;
}