Software & Finance





Visual C++ - Greatest Common Divisor (GCD) and Least Common Multiple (LCM)





I have given here the source code for calculating Greatest Common Divisor(GCD) and Least Common Multiple (LCM). I used the logic of prime number factors and common prime factors between the given two numbers to find the GCD. Once you know GCD, finding LCM is easy with the formula

LCM(a,b) = (a * b)/ GCD(a,b)



Source Code


#include <stdio.h>

#include <tchar.h>

#include <iostream>

 

#define MAX_SIZE 15000

 

bool IsPrimeNumber(int num)

{

    bool bPrime = true;

    int factor = num / 2;

    for(int i = 2; i <= factor; i++)

    {

        if( (num % i) == 0)

            bPrime = false;

    }

 

    return bPrime;

}

 

int GeneratePrimeNumbers(int max, int *arr)

{

    int idx = 0;

    for(int i = 2; i <= max; i++)

    {

        if(IsPrimeNumber(i) == true)

            arr[idx++] = i;

    }

    return idx;

}

 

 

int GetPrimeFactors(int num, int *arrResult)

{

    int idx = 0;

    int arr[MAX_SIZE];

    while(1)

    {

        if(IsPrimeNumber(num) == true)

        {

            arrResult[idx++] = num;

            return idx;

        }

        int count = GeneratePrimeNumbers(num, arr);

        for(int i = count - 1; i >= 0; i--)

        {

            if( (num % arr[i]) == 0)

            {

                arrResult[idx++] = arr[i];

                num = num / arr[i];

                break;

            }

        }

    }

    return idx;

}

 

int GetCommonPrimeFactors(int *arr1, int count1, int *arr2, int count2, int *arrResult)

{

    int idx = 0;

 

    for(int i = 0; i < count1; i++)

    {

        for(int j = 0; j < count2; j++)

        {

            if(arr2[j] < 0)

                continue;

            if(arr1[i] == arr2[j])

            {

                arrResult[idx++] = arr1[i];

                arr1[i] = arr2[j] = -1;

            }

        }

    }

    return idx;

}

 

int GetGCD(int num1, int num2, bool disp = false)

{

    int arr1[MAX_SIZE], arr2[MAX_SIZE], arrResult[MAX_SIZE];

 

    int count1 = GetPrimeFactors(num1, arr1);

    int count2 = GetPrimeFactors(num2, arr2);

 

    if(disp == true)

    {

        std::cout << "\nNumber1 " << num1 << " =";

        for(int i = 0; i < count1; i++)

        {

            std::cout << " " << arr1[i];

            if(i != count1 - 1)

                std::cout << " * ";

        }

 

 

        std::cout << "\nNumber2 " << num2 << " =";

        for(int j = 0; j < count2; j++)

        {

            std::cout << " " << arr2[j];

            if(j != count2 - 1)

                std::cout << " * ";

        }

    }

   

    int countResult = GetCommonPrimeFactors(arr1, count1, arr2, count2, arrResult);

 

    if(disp == true)

        std::cout << "\nGCD(" << num1 << "," << num2 << ") = " ;

 

    int gcd = 1;

    for(int k = 0; k < countResult; k++)

    {

        if(disp == true)

        {

            std::cout << arrResult[k];

            if(k != countResult - 1)

                std::cout << " * ";

        }

        gcd *= arrResult[k];

    }

    if(disp == true)

        std::cout << "\n\n";

    return gcd;

}

 

int GetLCM(int num1, int num2)

{

    return (num1 * num2) / GetGCD(num1, num2);

}

 

int main()

{

    int num1, num2;

 

    std::cout << "Enter First Number: ";

    std::cin >> num1;

    std::cout << "Enter Second Number: ";

    std::cin >> num2;

   

    int gcd = GetGCD(num1, num2, true);

    int lcm = GetLCM(num1, num2);

    std::cout << "GCD(" << num1 << "," << num2 << ") = " << gcd << "\n";

    std::cout << "LCM(" << num1 << "," << num2 << ") = " << lcm << "\n\n\n";

 

    return 0;

}

 


Click here to download the VS 2005 project and executable

 

 

Output


 

Enter First Number: 10

Enter Second Number: 135

 

Number1 10 = 5 *  2

Number2 135 = 5 *  3 *  3 *  3

GCD(10,135) = 5

 

GCD(10,135) = 5

LCM(10,135) = 270

 

 

Press any key to continue . . .