摘要
本文主要讲述了算术基本定理的内容，具体的应用形式，重点结合例题展示如何使用算术基本定理求解问题。
算术基本定理
算术基本定理可表述为：任何一个大于1的自然数 N,如果N不为质数，那么N可以唯一分解成有限个质数的乘积N=P1a1P2a2P3a3......Pnan，这里P1<P2<P3......<Pn均为质数，其中指数ai是正整数。这样的分解称为 N 的标准分解式。
算术基本定理是初等数论中一条非常基本和重要的定理，它把对自然数的研究转化为对其最基本的元素——素数的研究。唯一因子分解的思想从本质上讲是指以下两种性质： “存在性和唯一性”。所谓“存在性”就是指一个元素可以分解为有限多个不可约因子的乘积；“唯一性”是指这种分解表示在某种意义上来说是唯一的。
定理应用
算法实现
1 typedef long long ll; 2 const int maxn = 1e6 + 7; 3 ll a[maxn], b[maxn];//a[i]表示第i个质因子，b[i]表示第i个质因子的指数 4 void fac(ll n, int& tot) {//待分解的整数和不同质因数的个数（按引用传递） 5 ll tmp = (ll)(sqrt(n) + 0.5); 6 tot = 0; 7 ll now = n; 8 for(int i = 2; i <= tmp; i++) { 9 if(now % i == 0) { 10 a[++tot] = i; 11 b[tot] = 0; 12 while(now % i == 0) { 13 ++b[tot]; 14 now /= i; 15 } 16 } 17 } 18 if(now != 1) {//如果剩下的不是1，那就是最大的质因数19 a[++tot] = now; 20 b[tot] = 1; 21 } 22 }
可以用如下代码直接输出2 到100的质因数分解结果
View Code例题解析
