高中生程式解題:a010: 因數分解－資工趴趴熊的小天地

Content

各位在國小時都學過因數分解，都瞭解怎麼樣用紙筆計算出結果，現在由你來敎電腦做因數分解。

因數分解就是把一個數字，切分為數個質數的乘積，如 12=2^2 * 3

其中, 次方的符號以 ^ 來表示

Input

輸入共一行。每行包含一個整數，符合大於1 且小於等於 100000000

Output

針對每一行輸入整數輸出一個因數分解字串

Sample Input #1

Sample Output #1

2^2 * 5

Sample Input #2

Sample Output #2

Sample Input #3

Sample Output #3

757 * 1321

測資資訊：

記憶體限制： 64 MB
公開測資點#0 (6%): 1.0s , <1K
公開測資點#1 (6%): 1.0s , <1K
公開測資點#2 (6%): 1.0s , <1K
公開測資點#3 (6%): 1.0s , <1K
公開測資點#4 (6%): 1.0s , <1K
公開測資點#5 (6%): 1.0s , <1K
公開測資點#6 (6%): 1.0s , <1K
公開測資點#7 (6%): 1.0s , <1K
公開測資點#8 (6%): 1.0s , <1K
公開測資點#9 (6%): 1.0s , <1K
公開測資點#10 (6%): 1.0s , <1K
公開測資點#11 (6%): 1.0s , <1K
公開測資點#12 (7%): 1.0s , <1K
公開測資點#13 (7%): 1.0s , <1K
公開測資點#14 (7%): 1.0s , <1K
公開測資點#15 (7%): 1.0s , <1K

#include <iostream>
using namespace std;
 
int main() {
    int count;
    int factor,power; //factor因數 power次方 
    while (cin>>count){
        for (factor = 2; factor <= count; factor++){ //這裡記得要>=!!!不然最後數字會跑不出來
            power=0;

            while (count%factor==0){//這裡做短除法
                power++;
                count/=factor;
            }
/*-------------------------------------------------------*/
            //先討論次方，在討論因數
            if (power>1){ //若今天次方>1
                cout<<factor<<"^"<<power;
                if (count>1){cout<<" * ";} //除完後，剩下的數字還可以繼續除，所以中間放一個乘號 
            }
            else if (power==1){ //若次方為1，把因數輸出就好
                cout<<factor;
                if (count>1){cout<<" * ";}
            }

/*-------------------------------------------------------*/
            if (count==1){//除到最後了，要換行做下一個case
                cout<<"\n";
                break;
            }
        }
    }
    return 0;
}