各位在國小時都學過因數分解，都瞭解怎麼樣用紙筆計算出結果，現在由你來敎電腦做因數分解。
因數分解就是把一個數字，切分為數個質數的乘積，如 12 = 2^2 * 3。
其中, 次方的符號以 ^ 來表示
輸入共一行。每行包含一個整數，符合 大於 \(1\) 且 小於等於 \(1000000\)
針對每一行輸入整數輸出一個因數分解字串
| 輸入 | 輸出 |
|---|---|
20 |
2^2 * 5 |
17 |
17 |
999997 |
757 * 1321 |
這題會用到國中數學學到的短除法
在短除法中我們會先從2, 3, 5, 7…等依質數順序測試能否整除
i^p 輸出，接著檢查下一個質數。如何判斷是否為因數？
在程式中要判斷 \(a\) 是否為 \(b\) 的因數可以透過除法取餘數是否為零來判斷
例如 n % 2 == 0 即代表 \(2\) 是 \(n\) 的倍數
翻成中文是「\(n\) 除以 \(2\) ，餘數為 \(0\)」、「\(n\) 被 \(2\) 整除」、「 \(2\) 整除 \(n\) 」
做n的質因數分解，用空格隔開因數，先不處理次方、乘號
| 輸入 | 輸出 |
|---|---|
40 |
2 2 2 5 |
#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; }
加入一個計數器，紀錄同一個質因數有幾次方
| 輸入 | 輸出 |
|---|---|
40 |
2^3 * 5 |
#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; }
#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; }
一般程式的好習慣是 輸入->處理->輸出 ，所以我們可以將結果先存在陣列，最後再將將整個陣列輸出讓整個程式的架構更加清晰。
#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; } }
#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; } }