洛谷-P2043 质因子分解

题目描述

对N!进行质因子分解。

输入格式

输入数据仅有一行包含一个正整数N，N<=10000。

输出格式

输出数据包含若干行，每行两个正整数p,a，中间用一个空格隔开。表示N!包含a个质因子p,要求按p的值从小到大输出。

输入输出样例

输入

10

输出

2 8
3 4
5 2
7 1

---

#include <iostream>
#include <algorithm>
#include <map>

using namespace std;

map<int, int> m;

void decomposition(int n)
{
    for (int i = 2; i <= n; ++i) {
        while (n != i) {
            if (n % i == 0) {
                ++m[i];
                n /= i;
            }
            else break;
        }
    }
    ++m[n];
}

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

    int num;
    cin >> num;

    for (int i = 2; i <= num; ++i) decomposition(i);
    for (auto e : m) {
        cout << e.first << " " << e.second << endl;
    }

    return 0;
}