C Program to Find GCD and LCM of Two Numbers using Euclidean Algorithm

«
»
This is a C Program to find GCD and LCM of given two numbers. GCD is calculated using Euclidean Algorithm.

Here is source code of the C Program to Find the GCD and LCM of n Numbers. The C program is successfully compiled and run on a Linux system. The program output is also shown below.

  1. #include <stdio.h>
  2. #include <string.h>
  3. #include <stdlib.h>
  4.  
  5. int gcd(int x, int y) {
  6.     int r = 0, a, b;
  7.     a = (x > y) ? x : y; // a is greater number
  8.     b = (x < y) ? x : y; // b is smaller number
  9.  
  10.     r = b;
  11.     while (a % b != 0) {
  12.         r = a % b;
  13.         a = b;
  14.         b = r;
  15.     }
  16.     return r;
  17. }
  18.  
  19. int lcm(int x, int y) {
  20.     int a;
  21.     a = (x > y) ? x : y; // a is greater number
  22.     while (1) {
  23.         if (a % x == 0 && a % y == 0)
  24.             return a;
  25.         ++a;
  26.     }
  27. }
  28.  
  29. int main(int argc, char **argv) {
  30.     printf("Enter the two numbers: ");
  31.     int x, y;
  32.     scanf("%d", &x);
  33.     scanf("%d", &y);
  34.     printf("The GCD of two numbers is: %d", gcd(x, y));
  35.     printf("The LCM of two numbers is: %d", lcm(x, y));
  36.     return 0;
  37. }

Output:

$ gcc GCDLCM.c
$ ./a.out
 
Enter the two numbers: 12 15
The GCD of two numbers is: 3
The LCM of two numbers is: 60

Sanfoundry Global Education & Learning Series – 1000 C Programs.

advertisement
advertisement

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

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & technical discussions at Telegram SanfoundryClasses.