c++ 求解质因数（细节详解）

定义

这里先来了解几个定义（如已了解，可直接看下一个板块）

因数：又称为约数，如果整数a除以整数b（b0）的商正好是是整数而没有余数，我们就说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）！