gcd of two numbers in c | C Programming by TechWithCode

 GCD of Two Numbers in C

Hello and Welcome to www.TechWithCode.com

The World of Computer Science and Technology

Today we will learn about how to write a C Program to find the GCD of Two Numbers. Before moving forward, we must have knowledge about what GCD is?

What is GCD?

GCD stands for  Greatest Common Divisor. 

GCD of two or more integers, which are not all zero, is the largest positive integer that divides each of the integers. For two integers x, y, the greatest common divisor of x and y is denoted {gcd(x,y)}. 

For example, the GCD of 8 and 12 is 4, that is, {gcd(8,12)=4}

In order to find GCD, two scenarios occurred,

  1. Find GCD of two numbers

  2. Find GCD of Multiple Numbers (n Numbers)

Today we will write c programming code for both the scenarios one by one

To understand these Programs, you should have knowledge of the following C programming topics:

1. C Functions
2. C User-defined functions
3. C Recursion
4. C Lopping

  

1. Find GCD of two numbers

Problem Statement⤵️

Write a C program that calculates the GCD of two numbers, this number should be taken as input from the keyboard.

Source code⤵️

#include <stdio.h>
int hcf(int n1, int n2);
int main() {
    int n1, n2;
    printf("Enter two positive integers: ");
    scanf("%d %d", &n1, &n2);
    printf("G.C.D of %d and %d = %d", n1, n2, hcf(n1, n2));
    return 0;
}

int hcf(int n1, int n2) {
    if (n2 != 0)
        return hcf(n2, n1 % n2);
    else
        return n1;
}

output⤵️

2. Find GCD of Multiple Numbers (n Numbers)

Problem Statement⤵️

Write a C program that calculates the GCD of Multiple Numbers or N numbers, this number should be taken as input from the keyboard.

Source code⤵️

  
  #include<stdio.h>

int main()
{
   
    int x, y =- 1;
    printf("Enter numbers. To Calculate Enter 0\n");
    while(1)    // infinite loop to take input
    {
        scanf("%d", &x);
        if(x < 1)
            break;
        else if(y ==- 1)    // only 1 number entered, its GCD is itself
            y = x;
        else if(x < y)
            y = gcd(x, y);
        else
            y = gcd(y, x);
    }
    printf("\n\n\nGCD of all the entered number is: %d", y);
    
    return 0;
}

// GCD of 2 numbers is calculated at a time
int gcd(int a, int b) 
{
    int i;
    /*
        a is the smallest of the two numbers 
        of which GCD is to be calculated
    */
    for(i = a; i >= 1; i--) 
    {
        // Greatest number that divides both the numbers
        if(a%i == 0 && b%i == 0) 
            break;  // exits the loop
    }
    return i;
}
  
  

output⤵️