基本算数定理（唯一分解定理）

定义

基本算数定理，也称为唯一分解定理。

定理陈述：任何大于 1 的正整数，要么本身是质数，要么可以唯一地表示为若干个质数的乘积。

数学表达：

试除法分解质因子

前提知识

对于一个数字$n$，不会出现两个大于$\sqrt{n}$的因子。

为什么？

怎么用试除法分解质因子

枚举$[2,\sqrt{n}]$的所有数字，如果能整除n就一直除下去。直到枚举结束，剩余的数字如果大于1，那么就是那个大于$\sqrt{n}$的因子。

小优化：提前筛选出$[2,\sqrt{n}]$中的质数，每次枚举质数，降低时间复杂度。

代码实现

#include<iostream> using namespace std;const int N = 1e4;int n,c[N]; //c[N]：用于记录每个质因子出现的次数 int main()
{cin >> n;int x = n;for(int i=2;i<=n/i;i++){int cnt = 0;while(n % i == 0) {n /= i;cnt++;}c[i] += cnt;} if(n > 1) c[n]++;//输出质因数及其指数for(int i=2;i<=x;i++){if(c[i]) printf("%d^%d ",i,c[i]); } return 0;
}

时间复杂度

一般为$O(\sqrt{n})$，最优情况能达到$O(logn)$