---
title: 因數分解 presentation

---

<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` |

----

#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)*

#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)*

#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

#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 (如果看得懂，代表你已經很厲害了)

#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)