整数唯一分解定理(Unique decomposition theorem for integers)
适用级别：入门组
难度系数：3
OJ平台：P1658, LD1058
任何一个大于1的正整数都能唯一分解为有限个质数的乘积。
每个合数都可以写成几个质数相乘的形式，其中每个质数都是这个合数的因数，把一个合数用质因数相乘的形式表示出来，叫做分解质因数。如30=2×3×5 。分解质因数只针对合数。
代码实现一：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 | /**************************************************************** * Description: c++ prime factor * Author: Alex Li * Date: 2023-06-12 18:13:30 * LastEditTime: 2023-07-02 16:35:57 ****************************************************************/ #include <iostream> using namespace std; void primeFactors(int n){ int c=2; while(n>1){ if(n%c==0){ cout<<c<<" "; n/=c; } else c++; } } int main(){ int n; cin>>n; primeFactors(n); return 0; } |
代码实现二：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 | /**************************************************************** * Description: C++ implementation of Unique decomposition theorem for integers * Author: Alex Li * Date: 2023-06-21 10:44:25 * LastEditTime: 2023-06-21 11:08:12 ****************************************************************/ #include <iostream> using namespace std; vector<int>v;//存储唯一分解定理的分解值 void dev(int n){ int c=sqrt(n);//这里要单独提出来，否则下面for循环的时候n会变 for(int i=2;i<=c;++i){ //当n整除i的时候，就一直除到这个没办法再除为止 while(n%i==0)n/=i,v.push_back(i); //容易发现，经过这样的处理，绝对不会出来i是非素数的情况下n%i=0, //比如i=2的时候被n整除，n除i到没有办法再除以之后，n绝对不可能在之后整除4 } if(n!=1)//可能整除完还剩下一个数字， 这个数字一定是素数 v.push_back(n); } int main(){ int n; cin>>n; dev(n); for (int i = 0; i <v.size(); i++)cout<<v[i]<<' '; } |
计算约数的个数
一个合数N可以分解成若干质数的乘积。 N=Ae1*Be2*Ce3……. 例如 120=23*3*5
e1, e2,e3分别代表质数的次数
一个合数的约数个数 =(e1+1)(e2+1)(e3+1)…..(en+1) 其中，e1,e2,e3….en 是各个质因数的指数
120的约数=(3+1)(1+1)(1+1)=16
根据质因数分解，可以列出所有可能的组合：
20×30×50=1
21×30×50=2
22×30×50=4
23×30×50=8
20×31×50=3
21×31×50=6
22×31×50=12
23×31×50=24
20×30×51=5
21×30×51=10
22×30×51=20
23×30×51=40
20×31×51=15
21×31×51=30
22×31×51=60
23×31×51=120
代码演示：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 | /**************************************************************** * 代码作者: Alex Li * 创建时间: 2025-03-03 11:22:29 * 最后修改: 2025-03-03 12:06:37 * 文件描述: 求n的约数个数 ****************************************************************/ #include <bits/stdc++.h> using namespace std; vector<int> v; // dev 函数用于分解质因数并统计每个质因数的个数 void dev(int n){ // 这里要单独提出来，否则下面 for 循环的时候 n 会变 int c = sqrt(n); v.resize(n + 1); // 调整 v 的大小以适应 n for(int i = 2; i <= c; ++i){ // 当 n 能整除 i 的时候，就一直除到直到没办法再除为止，i <= sqrt(n) 就可以 while(n % i == 0){ n /= i; v[i]++; // 统计质因数 i 的个数 } // 容易发现，经过这样的处理，绝对不会出现 i 是非素数的情况下 n % i = 0, // 比如 i = 2 的时候被 n 整除，n 除 i 到没有办法再除为止，n 绝对不可能在之后整除 4 } if(n != 1) // 可能整除完还剩下一个数字，这个数字一定是素数 v[n]++; // 统计剩下的素数 } int main(){ int n, time = 1; cin >> n; dev(n); // 调用 dev 函数分解质因数 for (int i = 1; i <= n; i++){ if(v[i] != 0){ time *= v[i] + 1; // 计算约数的个数 } } cout << time; // 输出约数的个数 return 0; } |