<style> .reveal .slides { text-align: left; } </style> # [a010 因數分解](https://zerojudge.tw/ShowProblem?problemid=a010) --- ## Problem Description ---- 各位在國小時都學過因數分解，都瞭解怎麼樣用紙筆計算出結果，現在由你來敎電腦做因數分解。 因數分解就是把一個數字，切分為數個質數的乘積，如 `12 = 2^2 * 3`。 其中, 次方的符號以 `^` 來表示 ---- ##### 輸入說明 輸入共一行。每行包含一個整數，符合 大於 $1$ 且 小於等於 $1000000$ ##### 輸出說明 針對每一行輸入整數輸出一個因數分解字串 ---- ##### 範例輸入/輸出 | 輸入 | 輸出 | | -------- | ------------ | | `20` | `2^2 * 5` | | `17` | `17` | | `999997` | `757 * 1321` | --- ## 解題思路 ---- 這題會用到國中數學學到的**短除法** 在短除法中我們會先從2, 3, 5, 7...等依質數順序測試能否整除 ---- * 輸入數字 $n$ * 從2開始，一個一個檢查**質數**，判斷其是否為 $n$ 的 **因數** * 每找到一個**質因數** $i$，就用它去除 $n$，並將 $n$ 指定為新的 $n$ 值( $n$ 值會越來越小) * 用同一個質因數繼續除，並用一個變數 $p$ 紀錄該質因數除了幾次。 * 除到 $n$ 不能被它整除為止，即可將該質因數與次數 `i^p` 輸出，接著檢查下一個質數。 * 除到 $n$ 為 $1$ ，表示找到所有質因數了！ ---- ::: info **如何判斷是否為因數？** 在程式中要判斷 $a$ 是否為 $b$ 的因數可以透過除法取餘數是否為零來判斷 例如 `n % 2 == 0` 即代表 $2$ 是 $n$ 的倍數 翻成中文是「$n$ 除以 $2$ ，餘數為 $0$」、「$n$ 被 $2$ 整除」、「 $2$ 整除 $n$ 」 ::: --- #### Step 1. 只輸出質因數 ---- 做n的質因數分解，用空格隔開因數，先不處理次方、乘號 | 輸入 | 輸出 | | -------- | ------------ | | `40` | `2 2 2 5` | ---- ```cpp= #include<iostream> using namespace std; int main() { int n; // n: 要做質因數分解的數字 int i = 2; // i: 要拿來檢查的質因數。最小的質因數為2。 cin >> n; while( n > 1 ) // n=1 表示已經找完所有的質因數了。在這之前，一直找下去。 { while( n%i == 0 ) // 只要n能整除i，就一直做下去，直到不能整除為止。 { cout << i << " "; // 記得加空白，不然質因數會黏在一起。 n = n/i; } i++; // 不能整除，表示該換下一個質因數了。 } cout << endl; return 0; } ``` --- #### Step 2. 考慮次方 ---- 加入一個計數器，紀錄同一個質因數有幾次方 | 輸入 | 輸出 | | -------- | ------------ | | `40` | `2^3 * 5` | ---- :::spoiler 程式碼-1 *(By Paul)* ```cpp= #include <iostream> using namespace std; int main(){ int n; cin >> n; int i = 2; while(n>1){ if(n % i == 0){ //i是n的因數->除到不能再除為止 int p = 1; n /= i; while(n%i == 0){ p++; n /= i; // 跟 n = n/i 意思一樣 } if(p == 1) cout << i; else cout << i << "^" << p; if(n>1) // 後面還會有數字 cout << " * "; } i++; } cout << endl; } ``` ::: :::spoiler 程式碼-2 *(By Judy)* ``` cpp= #include <iostream> using namespace std; int main(){ int n; cin >> n; int i = 2; int p; // 計數器p while(n>1){ p = 0; // 換了一個質因數，重新計數。初始值為0 while(n%i == 0){ p++; n /= i; // 跟 n = n/i 意思一樣 } if(p>0){ if(p>1){ cout << i << "^" << p; } else if (p==1){ cout << i; } if(n>1){ cout << " * "; } } i++; } cout << endl; } ``` ::: --- #### Step 3. 進階挑戰－透過陣列儲存結果再輸出 ---- 一般程式的好習慣是 **輸入->處理->輸出** ，所以我們可以將結果先存在陣列，最後再將將整個陣列輸出讓整個程式的架構更加清晰。 ---- ::: spoiler 程式碼-1 ``` cpp= #include <iostream> using namespace std; int main(){ int n; cin >> n; /* 處理 */ int factor[15] = {0}; int pow[15] = {0}; int i = 2, num = 0; while(n>1){ int p = 0; // 換了一個質因數，重新計數。初始值為0 while(n%i == 0){ p++; n /= i; // 跟 n = n/i 意思一樣 } if(p>0){ factor[num] = i; pow[num] = p; num++; } i++; } /* 輸出 */ for(int i = 0; i < num; i++){ if(pow[i] > 1) cout << factor[i] << '^' << pow[i]; else cout << factor[i]; if(i < num-1) cout << " * "; else cout << endl; } } ``` ::: ::: spoiler 程式碼-2 (如果看得懂，代表你已經很厲害了) ```cpp= #include <iostream> using namespace std; int main(){ /* 輸入 */ int n; cin >> n; /*處理*/ int factor[15] = {2}; //想想為何初始值這樣設定？ int pow[15] = {0}; int num = 0; while(n>1){ while(n % factor[num] == 0){ n /= factor[num]; pow[num]++; } if(pow[num] == 0){ // 不是n的質因數->直接覆蓋 factor[num]++; } else{ // 是n的質因數->放下一格 factor[num+1] = factor[num]+1; num++; } } /* 輸出 */ for(int i = 0; i < num; i++){ if(pow[i] > 1) cout << factor[i] << '^' << pow[i]; else cout << factor[i]; if(i < num-1) cout << " * "; else cout << endl; } } ``` ::: --- ## 延伸思考？ ---- 1. 明明解題思路中是說一個一個檢查**質因數**，為何我們迴圈裡面的 $i$ 不用先判斷是不是質數？ ---- 2. 如果用陣列存下結果，那陣列開 $15$ 格會不夠嗎？至少需要開到幾格才夠？ --- [參考資料](https://www.csie.ntu.edu.tw/~b98902112/cpp_and_algo/basic_problem/factorization_sol.html)