C Program to Find GCD of two Numbers

In this post, you will learn how to find the GCD of two numbers using the C Programming language.

The GCD also known as HCF is the largest number that can be exactly divisible by both numbers without giving any remainder. Ex – GCD of 15 and 25 is 5.

Today, we will tell you three different  methods to find GCD. First by using Loop, Second method consists of Euclidean Algorithm and the last method helps you find GCD of both positive and negative numbers.

So, without further ado, let’s begin the tutorial.

C Program to Find GCD of two Numbers Using Loops

// C Program To Find GCD of Two Numbers
#include <stdio.h>
int main(){
    int a, b, gcd;
    
    // Asking for Input
    printf("Enter two numbers: \n");
    scanf("%d \n", &a);
    scanf("%d", &b);
    
    // logic
    for (int i = 1; i <= a && i <= b; i++){
        if ( a % i == 0 && b % i == 0){
            gcd = i;
        }
    }
    printf("GCD of %d and %d is: %d", a, b, gcd);
    return 0;
}

Output

Enter two numbers: 
4
24
GCD of 4 and 24 is: 4

How Does This Program Work ?

int main(){
    int a, b, gcd;

In this program, we have declared three int type variables named as a, b and gcd respectively.

    // Asking for Input
    printf("Enter two numbers: \n");
    scanf("%d \n", &a);
    scanf("%d", &b);

In this next step, the user is asked to enter the value of two numbers. This value will get stored in a and b variables.

    // logic
    for (int i = 1; i <= a && i <= b; i++){
        if ( a % i == 0 && b % i == 0){
            gcd = i;
        }

Now, for loop will be iterated until i is less than a and b. If both a and b are exactly divisible by i, then the value of i is assigned to gcd.

    printf("GCD of %d and %d is: %d", a, b, gcd);

In the last step, we print the GCD of two numbers which is stored in the gcd variable using printf() function.

Some of the used terms are as follow:

#include <stdio.h> – In the first line we have used #include, it is a preprocessor command that tells the compiler to include the contents of the stdio.h(standard input and output) file in the program. 

The stdio.h is a file which contains input and output functions like scanf() and printf() to take input and display output respectively. 

Int main() – Here main() is the function name and int is the return type of this function. The Execution of any Programming written in C language begins with main() function. 

Scanf() – scanf() function is used to take input from the user.   

printf() – printf() function is used to display and print the string under the quotation to the screen.  

for loop – A loop is used for initializing a block of statements repeatedly until a given condition returns false.

// – Used for Commenting in C.  

GCD Using Euclidean Algorithm

// GCD Using Euclidean Algorithm
#include <stdio.h>
int main(){
    int a, b, gcd;
    
    // Asking for Input
    printf("Enter two numbers: \n");
    scanf("%d \n", &a);
    scanf("%d", &b);
    
    // logic
    while(b){
        gcd = b;
        b = a % b;
        a = gcd;
    }
    printf("GCD of Two Numbers is: %d", a);
    return 0;
}

Output

Enter two numbers: 
4
16
GCD of Two Numbers is: 4

GCD for Both Positive and Negative Integers

// GCD for Both Positive and Negative Numbers
#include <stdio.h>
int main(){
    int a, b;
    
    // Asking for Input
    printf("Enter two numbers: ");
    scanf("%d %d", &a, &b);
    
    // Sign Conversion
    a = (a > 0) ? a : -a;
    b = (b - 0) ? b : -b;
    
    // logic
    while (a != b){
        if (a > b)
            a -= b;
        else    
            b -= a;
    }
    printf("GCD of Two Numbers is: %d", a);
    return 0;
}

Output

Enter two numbers: 4 60
GCD of Two Numbers is: 4

Conclusion

I hope after going through this post, you understand how to find the GCD of two numbers using C Programming language.

If you have any doubt regarding the topic, feel free to contact us in the Comment Section. We will be delighted to help you.