唯一分解定理

理论

1. 算术基本定理（唯一分解定理）
   每个正整数都能够唯一的表示成它的质因数的乘积。
   例如，$280=2^3\ast 5^1\ast 7^1$

2. $n$ 中最多只含有一个大于 $\sqrt{n}$ 的因子
   反证法：如果有两个大于 $\sqrt{n}$ 的因子，则相乘会大于 $n$

3. 分解质因数
   在 $2\sim \sqrt{n}$ 范围枚举，
   遇到质因子就除净并且记录质因子的个数。
   最后如果 $n>1$，说明这就是那个大于 $\sqrt{n}$ 的质因子。

模板

int a[10001];//质因子的个数
void decompose(int x) {//分解质因子for (int i = 2; i * i <= x; i++) {while (x % i == 0) {a[i]++;x /= i;}}if (x > 1) {a[x]++;}
}

模拟：x=280
i=2, a[2]=3, x=35
i=3, 4,
i=5, a[5]=1, x=7
7>1, a[7]=1

例题

P2043 质因子分解

题目描述
对 $N!$ 进行质因子分解。

输入格式
输入数据仅有一行包含一个正整数 $N$，$N\le 10000$。

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

输入输出样例 #1
输入 #1

10

输出 #1

2 8
3 4
5 2
7 1

说明/提示
$10!=3628800=(2^8)\times (3^4)\times (5^2)\times 7$。

#include<bits/stdc++.h>
using namespace std;
int n;
int a[10001];//质因子的个数
void decompose(int x) {//分解质因子for (int i = 2; i * i <= x; i++) {while (x % i == 0) {a[i]++;x /= i;}}if (x > 1) {a[x]++;}
}
int main() {cin >> n;//n!=1*2*3*4*...*nfor (int i = 1; i <= n; i++) {decompose(i);}for (int i = 1; i <= n; i++) {if (a[i]) {cout << i << " " << a[i] << endl;}}return 0;
}