Showing posts with label GCD. Show all posts
Showing posts with label GCD. Show all posts

C Program to Find the GCD and LCM of Two Integers



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.
1.  /*
2.   * C program to find the GCD and LCM of two integers using Euclids' algorithm
3.   */
4.  #include <stdio.h>
5.   
6.  void main()
7.  {
8.      int num1, num2, gcd, lcm, remainder, numerator, denominator;
9.   
10.    printf("Enter two numbers\n");
11.    scanf("%d %d", &num1, &num2);
12.    if (num1 > num2)
13.    {
14.        numerator = num1;
15.        denominator = num2;
16.    }
17.    else
18.    {
19.        numerator = num2;
20.        denominator = num1;
21.    }
22.    remainder = num1 % num2;
23.    while (remainder != 0)
24.    {
25.        numerator   = denominator;
26.        denominator = remainder;
27.        remainder   = numerator % denominator;
28.    }
29.    gcd = denominator;
30.    lcm = num1 * num2 / gcd;
31.    printf("GCD of %d and %d = %d\n", num1, num2, gcd);
32.    printf("LCM of %d and %d = %d\n", num1, num2, lcm);
33.}

Output:

Enter two numbers
30
40
GCD of 30 and 40 = 30
LCM of 30 and 40