LCM and HCF in C Using Euclid’s Algorithm

Complete C program for HCF and LCM

#include <errno.h>
#include <limits.h>
#include <stdio.h>
#include <stdlib.h>

int parse_nonnegative(const char *text,
                      unsigned long long *value) {
    if (text[0] == '\0' || text[0] == '-') {
        return 0;
    }

    char *end;
    errno = 0;
    unsigned long long parsed = strtoull(text, &end, 10);
    if (errno == ERANGE || *end != '\0') {
        return 0;
    }

    *value = parsed;
    return 1;
}

unsigned long long gcd(unsigned long long a,
                       unsigned long long b) {
    while (b != 0) {
        unsigned long long remainder = a % b;
        a = b;
        b = remainder;
    }
    return a;
}

int main(void) {
    unsigned long long a, b;
    char first[32], second[32];

    printf("Enter two non-negative integers: ");
    if (scanf("%31s %31s", first, second) != 2 ||
        !parse_nonnegative(first, &a) ||
        !parse_nonnegative(second, &b)) {
        fprintf(stderr, "Invalid input.\n");
        return 1;
    }

    unsigned long long hcf = gcd(a, b);
    printf("HCF/GCD = %llu\n", hcf);

    if (a == 0 || b == 0) {
        printf("LCM = 0\n");
        return 0;
    }

    unsigned long long scaled = a / hcf;
    if (scaled > ULLONG_MAX / b) {
        fprintf(stderr, "LCM exceeds unsigned long long.\n");
        return 1;
    }

    unsigned long long lcm = scaled * b;
    printf("LCM = %llu\n", lcm);
    return 0;
}

How the C program works

1. Find HCF with the Euclidean algorithm

The function repeatedly computes a % b. Each iteration replaces the pair with the previous divisor and remainder. When the remainder reaches zero, the remaining value of a is the HCF.

2. Handle zero explicitly

The program uses gcd(0,n) = n and lcm(0,n) = 0. This branch also avoids dividing by zero when both inputs are zero.

3. Divide before multiplying

Writing (a / hcf) * b generally produces a smaller intermediate value than a * b / hcf. The comparison with ULLONG_MAX / b checks whether the final multiplication fits in the selected unsigned integer type.

Sample input and output

Enter two non-negative integers: 48 180
HCF/GCD = 12
LCM = 720

The result satisfies 12 × 720 = 48 × 180 = 8640.

Verify 48 and 180 online

Useful test cases

Common C mistakes

• Calculating a * b before dividing, which can overflow unnecessarily.
• Using a loop that starts at 1 and checks every possible factor; Euclid’s algorithm is simpler and faster.
• Forgetting that scanf can fail and leave values uninitialized.
• Dividing by the GCD before handling the all-zero case.
• Using signed input without defining how negative values should be normalized.

Frequently asked questions

Calculator and further reference

Run examples and view every Euclidean division in the GCD, HCF and LCM calculator. If you need the underlying definitions and help choosing the right operation, read what LCM and HCF mean in maths. A simpler introductory implementation is available in Programiz’s C LCM example; this guide adds zero and overflow handling.