a010 因數分解

Problem Description

各位在國小時都學過因數分解，都瞭解怎麼樣用紙筆計算出結果，現在由你來敎電腦做因數分解。
因數分解就是把一個數字，切分為數個質數的乘積，如 12 = 2^2 * 3。其中, 次方的符號以 ^ 來表示

輸入說明

輸入共一行。每行包含一個整數，符合 大於

$1$ 且 小於等於

$1000000$

輸出說明

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

範例輸入/輸出

輸入	輸出
20	2^2 * 5
17	17
999997	757 * 1321

解題思路

這題會用到國中數學學到的短除法

• 輸入數字
  $n$
• 從2開始，一個一個檢查質數，判斷其是否為
  $n$ 的 因數
• 每找到一個質因數
  $i$，就用它去除
  $n$，並將
  $n$ 指定為新的
  $n$ 值(
  $n$ 值會越來越小)
• 用同一個質因數繼續除，並用一個變數
  $p$ 紀錄該質因數除了幾次。
• 除到
  $n$ 不能被它整除為止，即可將該質因數與次數 i^p 輸出，接著檢查下一個質數。
• 除到
  $n$ 為
  $1$ ，表示找到所有質因數了！

如何判斷是否為因數？

在程式中要判斷

$a$ 是否為

$b$ 的因數可以透過除法取餘數是否為零來判斷
例如 n % 2 == 0 即代表

$2$ 是

$n$ 的倍數
翻成中文是「

$n$ 除以

$2$ ，餘數為

$0$」、「

$n$ 被

$2$ 整除」、「

$2$ 整除

$n$ 」

Sample Code

參考資料

Step 1. 做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;
}

Step 2. 加入一個計數器，紀錄同一個質因數有幾次方

輸入	輸出
40	2^3 * 5

程式碼-1 (By Paul)

#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;
}

程式碼-2 (By Judy)

#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. 進階挑戰－透過陣列儲存結果再輸出

一般程式的好習慣是 輸入->處理->輸出 ，所以我們可以將結果先存在陣列，最後再將將整個陣列輸出讓整個程式的架構更加清晰。

程式碼-1

#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;
    }
}

程式碼-2 (如果看得懂，代表你已經很厲害了)

#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$ 格會不夠嗎？至少需要開到幾格才夠？