分解质因数
1. 定义
把一个合数分解成若干个质因数的乘积的形式，即求质因数的过程叫做分解质因数。如60=2×2×3×5
质因数也称为质因子或素因数。
性质1：质数分解的结果是唯一的。
2. 短除法
从最小的质数除起，一直除到结果为质数为止。分解质因数的算式叫短除法，和除法的性质相似。例如:
得到 360=2×2×2×3×3×5。
参考程序1：
输入100，输出2 2 5 5。
请思考：程序的第20句中为什么如果i是因子就一定是质因子。
短除法：
如果追求程序的简洁性，可以省略prime函数。
参考程序2
思考题：“参考程序2”的正确性。
**进一步思考：参考程序1和参考程序2的时间复杂度是多少？
筛选法：
前面的求质数筛选法中，可以求出2到N的每个数i的最小质因数P[i]。利用这个预处理，可以得到一种迭代的分解质因数方法：
问题：对A进行分解质因数。
已知A的最小质因数是P[A]，令A’=A/P[A]；
原问题可以转换为子问题：对A’进行分解质因数。
迭代处理，直到A’没有最小质因数。
参考程序3：（填空）
|
//筛选法分解质因数 #include <bits/stdc++.h> using namespace std; int N,A,P[1000001]; int main(){ cin >>N; P[1]=1; for (int i=2; i*i<=N; i++) if (P[i]==0){ //质数 for (int j=i+i; j<=N; j+=i)//i是质数时，删除i的倍数 if (P[j]==0) P[j]=i; } for (A=N; P[A]>0; A=A/P[A] ) //A迭代变小 cout <<P[A]<<" "; cout << A; return 0; }文章来源：https://www.toymoban.com/news/detail-439932.html |
对于求2到N的所有数分解质因数时，效率很高。文章来源地址https://www.toymoban.com/news/detail-439932.html
到了这里，关于c++分解质因数详解的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
![[保研/考研机试] KY7 质因数的个数 清华大学复试上机题 C++实现](https://imgs.yssmx.com/Uploads/2024/02/643947-1.png)
