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

{

arr[idx++] = i;

}

return idx;

}

int GetPrimeFactors(int num, int *arrResult)

{

int idx = 0;

int arr[MAX_SIZE];

while(1)

{

{

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;

}

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