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.

```
#include <stdio.h>
```
```
#include <string.h>
```
```
#include <stdlib.h>
```
```
 
```
```
int gcd(int x, int y) {
```
```
    int r = 0, a, b;
```

    a = (x > y) ? x : y; // a is greater number

    b = (x < y) ? x : y; // b is smaller number

```
 
```
```
    r = b;
```
```
    while (a % b != 0) {
```
```
        r = a % b;
```
```
        a = b;
```
```
        b = r;
```
```
    }
```
```
    return r;
```
```
}
```
```
 
```
```
int lcm(int x, int y) {
```
```
    int a;
```

    a = (x > y) ? x : y; // a is greater number

```
    while (1) {
```
```
        if (a % x == 0 && a % y == 0)
```
```
            return a;
```
```
        ++a;
```
```
    }
```
```
}
```
```
 
```
```
int main(int argc, char **argv) {
```
```
    printf("Enter the two numbers: ");
```
```
    int x, y;
```
```
    scanf("%d", &x);
```
```
    scanf("%d", &y);
```

    printf("The GCD of two numbers is: %d", gcd(x, y));

    printf("The LCM of two numbers is: %d", lcm(x, y));

```
    return 0;
```
```
}
```

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.

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

« Prev - C Program to Perform Addition using Bitwise Operators

» Next - C Program to Represent Linear Equations in Matrix Form

Related Posts:

Practice BCA MCQs
Check Computer Science Books
Practice Computer Science MCQs
Apply for C Internship
Check C Books

Recommended Articles: