Software & Finance





C Programming (Turbo C++ Compiler) - 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). GCD can be found with a simple while loop by comaring the two numbers and assigning the difference to the largest number until the two numbers are equal. Once you know GCD, finding LCM is easy with the formula.

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


Source Code


#include <stdio.h>

 

 

int GetGCD(int num1, int num2)

{

       while(num1!=num2)

       {

       if(num1 > num2)

              num1 = num1 - num2;

       if(num2 > num1)

              num2 = num2 - num1;

       }

       return num1;

}

 

int GetLCM(int num1, long num2)

{

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

}

 

long main()

{

    long num1, num2;

    long gcd, lcm;

 

    printf("Enter First Number: ");

    scanf("%d", &num1);

 

    printf("Enter Second Number: ");

    scanf("%d", &num2);

 

    gcd = GetGCD(num1, num2);

    lcm = GetLCM(num1, num2);

 

    printf("\nGCD(%d,%d) = %d\n", num1, num2, gcd);

    printf("\nLCM(%d,%d) = %d\n\n\n", num1, num2, lcm);

 

    return 0;

}

 

Output


 

Enter First Number: 10

Enter Second Number: 135

 

GCD(10,135) = 5

LCM(10,135) = 270

 

 

Press any key to continue . . .