GCD means Greatest Common Divisor. For two
integers a and b, if there are any numbers d so that a/d and b/d doesn’t have
any remainder, such a number is called a common divisor. Common divisors exist
for any pair of integers a and b, since we know that 1 always divides any
integer. We also know that common divisors cannot get too big since divisors
cannot be any larger than the number they are dividing. Hence a common divisor
d of a and b must have d <= a and d <= b.
LCM means Least Common Multiplies. For two integer
a and b, to know if there are any smallest numbers d so that d/a and d/b
doesn't have a remainder. Such a number is called a Least Common Multiplier.
Here is source code of the C program to calculate
the GCD and LCM of two integers. It compiles and runs on any operating system.
Method 1:
#include <stdio.h>
int main() {
int a, b, x, y, t, gcd, lcm;
printf("Enter Two Integers: ");
scanf("%d%d", &x, &y);
if (x==0 || y==0)
{
printf("\n\nWRONG INPUT. TRY
ANOTHER VALUE\n\n");
return 0;
}
a = x;
b = y;
while (b != 0) {
t = b;
b = a % b;
a = t;
}
gcd = a;
lcm = (x*y)/gcd;
if(gcd < 0) { gcd = -gcd; }
if(lcm < 0) { lcm = -lcm; }
printf("\n\nGreatest Common Divisor Of %d and
%d = %d\n\n", x, y, gcd);
printf("Least Common Multiple Of %d and %d =
%d\n\n", x, y, lcm);
return 0;
}
Method 2:
#include <stdio.h>
long gcd(long, long);
int main() {
long x, y, hcf, lcm;
printf("Enter Two Integers: ");
scanf("%ld%ld", &x, &y);
if (x==0 || y==0)
{
printf("\n\nWRONG INPUT. CHANGE ZERO AND TRY
ANOTHER VALUE\n\n");
return 0;
}
hcf = gcd(x, y);
lcm = (x*y)/hcf;
if(hcf < 0) { hcf = -hcf; }
if(lcm < 0) { lcm = -lcm; }
printf("\n\nGreatest Common Divisor Of %ld
and %ld = %ld\n\n", x, y, hcf);
printf("Least Common Multiple Of %ld and %ld
= %ld\n\n", x, y, lcm);
return 0;
}
long gcd(long a, long b)
{
if (b == 0)
{
return a;
}
else
{
return gcd(b, a % b);
}}