HCF / GCD of Numbers in C

The highest common factor (HCF), also called the greatest common divisor (GCD), is the largest positive integer that divides both numbers exactly. The Euclidean algorithm finds it efficiently without listing every factor.

GCD with the Euclidean Algorithm Top ↑

#include <stdio.h>

int gcd(int a, int b) {
    if (a < 0) a = -a;
    if (b < 0) b = -b;

    while (b != 0) {
        int remainder = a % b;
        a = b;
        b = remainder;
    }

    return a;
}

int main(void) {
    int first = 56;
    int second = 98;

    printf("GCD of %d and %d = %d\n",
           first, second, gcd(first, second));

    return 0;
}

Output

GCD of 56 and 98 = 14

GCD from User Input Top ↑

#include <stdio.h>

int gcd(int a, int b) {
    if (a < 0) a = -a;
    if (b < 0) b = -b;

    while (b != 0) {
        int remainder = a % b;
        a = b;
        b = remainder;
    }

    return a;
}

int main(void) {
    int first;
    int second;

    printf("Enter two integers: ");
    if (scanf("%d %d", &first, &second) != 2) {
        printf("Invalid input.\n");
        return 1;
    }

    if (first == 0 && second == 0) {
        printf("GCD is undefined for 0 and 0.\n");
        return 0;
    }

    printf("GCD = %d\n", gcd(first, second));
    return 0;
}

Recursive GCD Top ↑

#include <stdio.h>

int gcd_recursive(int a, int b) {
    if (a < 0) a = -a;
    if (b < 0) b = -b;

    if (b == 0) {
        return a;
    }

    return gcd_recursive(b, a % b);
}

int main(void) {
    int first = 48;
    int second = 18;

    printf("GCD = %d\n",
           gcd_recursive(first, second));

    return 0;
}

Output

GCD = 6

GCD of Multiple Numbers Top ↑

#include <stdio.h>

int gcd(int a, int b) {
    if (a < 0) a = -a;
    if (b < 0) b = -b;

    while (b != 0) {
        int remainder = a % b;
        a = b;
        b = remainder;
    }

    return a;
}

int gcd_multiple(const int values[], size_t count) {
    int result = 0;

    for (size_t i = 0; i < count; i++) {
        result = gcd(result, values[i]);
    }

    return result;
}

int main(void) {
    int values[] = {120, 180, 240};
    size_t count = sizeof values / sizeof values[0];

    printf("GCD = %d\n",
           gcd_multiple(values, count));

    return 0;
}

Output

GCD = 60

Related Factor Tutorials Top ↑

• Factors of one number
• All common factors of two numbers

Subhendu Mohapatra

Author & Instructor at plus2net

I write and maintain practical tutorials on Python, PHP, SQL, JavaScript, HTML, jQuery, and web development at plus2net. The tutorials focus on clear explanations, working examples, and code that readers can test and adapt while learning.

About the author   Watch on YouTube

Connect: