c++分解质因数

问题描述： 一个任意输入的整形数分解质因数M , 并以 M=N*P*Q*R ...的形式输出。

分析：对于任意输入的整形数M,我们可以从最小的质素2开始（记为K）依次递增判读能否整除M, 知道找到一个能整除M的数， 记录此时的K，然后让M=M/K , 然后让K重新等于2，开始找下一个因数。知道最后剩余的M不能分解

示例代码：

#include <iostream> #include <sstream> using namespace std; int main(){ int M;    //输入的数M string result= "1";  //字符串，用来记录结果 cin>>M; for(int i=2;i<M;){   //从最小的质素2,到最大的M 通过遍历找M的因子   if( M%i == 0 ){ // 找到因子 i         //将i转换成string ，并追加到结果串中         stringstream  resultT;  //用来转换整形为string 的临时变量         resultT<<i;    result = result + "*" +  resultT.str();     // 把M除以已经找到的因子，让i=2, 开始找下一个因子     M=M/i;     i=2;    }else{     i++;    }   }  // 当循环到 i=M-1还是没有找到M的因数，说明M已经为质数，追加M到结果串并打印   cout<<result<<"*"<<M<<endl; }

运行效果：

[email protected]:~/Documents/c++/class4$ ./function 124 1*2*2*31 [email protected]:~/Documents/c++/class4$ ./function 12 1*2*2*3 [email protected]:~/Documents/c++/class4$