分解质因子

分解质因子

题目描述

将一个正整数分解质因数，例如，输入90，输出2 3 3 5。

输入

输入一个正整数n（2<=n<=2000）。

输出

从小到大输出n的所有质因子，每两个数之间空一格。

样例输入

20

样例输出

2 2 5

解

这道题感觉挺难办的猛一看，质数判断我会，但让我分解质因数，总感觉有些复杂

等到真正写出来，就感觉，嘶，这小东西挺别致哈。

这个我从数的角度简单分析一下，如果这个数可分解为若干个质因数，那首先分解出来的应该是2、3、5这些值较小的质数，而且往往会分解出来多个，所以可以进行一个循环判断，并在每次分解之后，原来值的规模会缩减对应的倍数，比如20分解出两个2之后，原值缩减为5；若遍历值大于原值开方，就可以结束了，实际上循环结束的判断与质数判断有异曲同工之妙。当然，也有可能本身输入的就是质数，而经过前面的循环之后得到的值也一定是一个质数，最后再记得输出一下即可。

我分享一下参考代码，大家可以跟着理解理解

#include<bits/stdc++.h>using namespace std;int main() {int n;vector<int> a; // 用于存储质因数cin >> n;for(int i = 2; i <= sqrt(n) + 1; i++) {while(n % i == 0) {a.push_back(i);n /= i;}}if(n >= 2) // 若最后有剩余大于1的值，也要记得输出a.push_back(n);for(int i = 0; i < a.size(); i++) { // 格式化输出if(i == 0) cout << a[i];else cout << ' ' << a[i];}return 0;
}

看看腿