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$