Saturday, March 7, 2015

Calculating the HCF and LCM of two numbers

Here is the program to calculate the Highest Common Factor (HCF -- also known as Greatest Common Divisor) and Lowest Common Multiple (LCM) of two numbers. The code is extremely simple.


#include <stdio.h>

int main()
    unsigned int a, b, i, hcf;
    printf("Enter two positive integers > 0: ");
    scanf("%d%d", &a, &b);
    for(i=1; i<=(a<b? a: b); i++)
        if(!(a%i) && !(b%i))
            hcf = i;
    printf("\nThe HCF of %d and %d is %d\n", a, b, hcf);
    printf("The LCM of %d and %d is %d\n", a, b, ((a*b)/hcf));
    return 0;


HCF is obtained by dividing both numbers with all natural numbers less than the smallest one and choosing the last common factor (which will be the highest) encountered in the for loop. [The expression (a<b? a: b) chooses the smallest of a and b. The special operator ?: is technically known as conditional operator.]
LCM is calculated using the formula LCM = (a*b)/HCF.


Enter two positive integers > 0: 4 6

The HCF of 4 and 6 is 2
The LCM of 4 and 6 is 12

No comments:

Post a Comment