[C++][東方哈佛電機系] 資概作業5_gcd 和lcm 的質因數分解



#include <iostream>
#include <cmath>
using namespace std;


void decomposition(int);

int main()
{
        do{

        //////////////////////////////////
        // stage1: 判斷是否進入運算
        //////////////////////////////////
        int a, b;
       
        cout << endl;

        cout << "Please input a natural number a: ";
        cin >> a;
        if (a <= 0){
                system("pause");
                return 0;
        }

        cout << "Please input a natural number b: ";
        cin >> b;
        if (b <= 0){
                system("pause");
                return 0;
        }



        ////////////////////////////////
        // stage2: GCD
        ////////////////////////////////
        int gcd;
        int large, small, remainder;

        large = (a >=b ) ? a:b;
        small = (large == a) ? b:a;

        while ((remainder = large % small) != 0){
                large = small;
                small = remainder;
        }

        // GCD = small;
        gcd = small;




        ////////////////////////////////
        // stage3: LCM
        ////////////////////////////////
        int lcm, remainA, remainB;

        remainA = a / gcd;
        remainB = b / gcd;

        lcm = gcd * remainA * remainB;




        ////////////////////////////////////////
        // stage: prime factor decomposition
        ////////////////////////////////////////

        printf("(%d, %d) = %d = ", a, b, gcd);
        decomposition(gcd);
        printf("\n");

        printf("[%d, %d] = %d = ", a, b, lcm);
        decomposition(lcm);
        printf("\n");


        }while(1);

}

void decomposition(int value)
{
        int limit,
        i, k,
                temp = value,
                numFactor = 0,
        numPower;
       
        limit = value;

        for (i=2 ; i<=limit ; i++){
       
        // 檢查質因數與相應次方
        numPower = 0;
                while ((limit > 0) && (limit%i == 0)){
            limit /= i;
            numPower++;
                }
               
                // 印出質因數相乘結果
        if ((limit != 1) && (numPower != 0))         // A-1) 非最後一個質因數
        {
            if (numPower == 1)   // B-1) 不印出次方
                printf("(%d) * ", i);
            else                 // B-2) 印出次方
                printf("(%d^%d) * ", i, numPower);
        }
        else if ((limit == 1) && (numPower != 0))    // A-2) 最後一個質因數
        {
            if (numPower == 1)   // B-1) 不印出次方
                printf("(%d) ", i);
            else                 // B-2) 印出次方
                printf("(%d^%d) ", i, numPower);
        } 
        }

}