自学内容网 自学内容网

c++ 求解质因数(细节详解)

定义

这里先来了解几个定义(如已了解,可直接看下一个板块)

因数:又称为约数,如果整数a除以整数b(b\neq0)的商正好是是整数而没有余数,我们就说b是a的因数

质数:又称为素数,一个大于1的自然数,除了1和它自身外,不能被其他自然数整除的数叫做质数。2是最小的质数

质因数:如果一个数a的因数b同时也是质数,那么b就是a的质因数,例如:8=2*2*2,2就是8的质因数;12=2*2*3,2和3就是12的质因数

了解了质因数的定义后,我们借一道题(自创,为方便大家理解题目,我尽量做到简洁)来了解如何求解质因数(这道题演示的是求解质因数的基础模板,如有其他需求,可以在此模板上延伸)

题目 

题目描述

输入一个整数n,输出此数的所有质因数

输入描述

输入一个整数n

输出描述

输出n的所有质因数

样例输入

12

样例输出

2 2 3

解题思路

上面的样例数字太小,不便于发现规律,所以我们以180来举例,它的质因数为2,2,3,3,5

我们可以发现,质因数由大到小依次寻找,且最小的质数为2,最大的质因数永远不会超过数字本身(如7的质因数就为7,等于本身)

如此一来,便有了如下for循环:

for(int i=2;i<=n;i++){
while(n%i==0){
cout<<i<<" ";
n/=i;
}
}

很多人看到这个for循环发现根本没有判断质数,便确认这是错的,但我们仔细研究一下其中的while循环,并结合180的质因数来思考:

180的质因数中含有两个2,而我们这里的for循环是用来遍历从2到n所有的数,如果n除以i的商还能除以i,那就一直除下去,直到n除以i的商不能除以i为止,才继续遍历下一个数来除

那为什么没有判断质数还能检测出质因数呢?

因为所有的合数都是由质因数组合而成的,经过前面循环地除以i,那么以i为因数的其他数就没有被遍历的可能(因为这个数已经被分解)

而由于遍历时的被除数为n除以i的商,所以每次n都要除以i,并将n刷新为n除以i的商,这便是n/=i;的含义

到这里,for循环的含义已经讲解完毕,此程序的核心也宣告结束,接下来只需输入加输出

贴代码时间!

总代码

非常的少,准备好了吗?

#include<iostream>
using namespace std;
int main(){
int n;
cin>>n;
for(int i=2;i<=n;i++){
while(n%i==0){
cout<<i<<" ";
n/=i;
}
}
}

运行结果:

如对本文有疑惑欢迎评论区留言或私信! 


原文地址:https://blog.csdn.net/dfr110719/article/details/140672926

免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!