c++分解质因数
分解质因数
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; } |
对于求2到N的所有数分解质因数时,效率很高。
这篇好文章是转载于:学新通技术网
- 版权申明: 本站部分内容来自互联网,仅供学习及演示用,请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系,请提供相关证据及您的身份证明,我们将在收到邮件后48小时内删除。
- 本站站名: 学新通技术网
- 本文地址: /boutique/detail/tanhgekfja
-
photoshop保存的图片太大微信发不了怎么办
PHP中文网 06-15 -
Android 11 保存文件到外部存储,并分享文件
Luke 10-12 -
《学习通》视频自动暂停处理方法
HelloWorld317 07-05 -
word里面弄一个表格后上面的标题会跑到下面怎么办
PHP中文网 06-20 -
photoshop扩展功能面板显示灰色怎么办
PHP中文网 06-14 -
微信公众号没有声音提示怎么办
PHP中文网 03-31 -
excel下划线不显示怎么办
PHP中文网 06-23 -
excel打印预览压线压字怎么办
PHP中文网 06-22 -
怎样阻止微信小程序自动打开
PHP中文网 06-13 -
TikTok加速器哪个好免费的TK加速器推荐
TK小达人 10-01