藍橋杯 ADV-223 因式分解

問題描述

設計算法，使用者輸入合數，程式輸出若個素數的乘積。例如，輸入6，輸出2*3。輸入20，輸出2*2*5。

輸入樣例

120

輸出樣例

2*2*2*3*5

思路解析

• 篩選出5000内的素數，從頭到尾進行取餘，餘數為0，則該素數為因子，餘數不為0，則疊代至下一個素數，直到該數為1。

#include<iostream>
#include<vector>

using namespace std;

bool isPrime(int num){
    if (num == 0 || num == 1)
        return false;
    for (int i = 2; i * i <= num; i++){
        if (num % i == 0)
            return false;
    }
    return true; 
}

int main() {
    int cn, index = 0;
    vector<int> pm, res;

    cin >> cn;

    for (int i = 0; i < 50000; i++){
        if (isPrime(i)){
            pm.push_back(i);
        }
    }
    index = 0;
    while (cn != 1){
        if (cn % pm[index] == 0){
            cn /= pm[index];
            res.push_back(pm[index]);
        }
        else
            index++;        
    }
    cout << res[0];
    for (int i = 1; i < res.size(); i++){
        cout << "*";
        cout << res[i];
    }
    return 0;
}