This C Program calculates the GCD and LCM of two integers. Here 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 can’t get too big since divisors can’t 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. Here, LCM means Least Common Multiplies. For two integer a & 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. The C program is successfully compiled and run on a Linux system. The program output is also shown below.

`/*`

`* C program to find the GCD and LCM of two integers using Euclids' algorithm`

`*/`

`#include <stdio.h>`

void main()

`{`

int num1, num2, gcd, lcm, remainder, numerator, denominator;

printf("Enter two numbers\n");

scanf("%d %d", &num1, &num2);

if (num1 > num2)

`{`

numerator = num1;

denominator = num2;

`}`

`else`

`{`

numerator = num2;

denominator = num1;

`}`

remainder = numerator % denominator;

while (remainder != 0)

`{`

numerator = denominator;

denominator = remainder;

remainder = numerator % denominator;

`}`

gcd = denominator;

lcm = num1 * num2 / gcd;

printf("GCD of %d and %d = %d\n", num1, num2, gcd);

printf("LCM of %d and %d = %d\n", num1, num2, lcm);

`}`

advertisement

$ cc pgm11.c $ a.out Enter two numbers 30 40 GCD of 30 and 40 = 10 LCM of 30 and 40 = 120

**Sanfoundry Global Education & Learning Series – 1000 C Programs.**

advertisement

Here’s the list of Best Reference Books in C Programming, Data-Structures and Algorithms

If you wish to look at other example programs on Mathematical Functions, go to C Programming Examples on Mathematical Functions. If you wish to look at programming examples on all topics, go to C Programming Examples.