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