Program to Find LCM and HCF of two numbers

LCM stands for Least Common Multiple, and HCF stands for Highest common factor. Finding LCM and HCF of two numbers is an elementary school math problem. The HCF is also known as GCD (Greatest Common Divisor). You may know how to calculate LCM and HCF of two numbers using pen and paper.

Now, let's write a program that can accept two numbers from the user and return their LCM and HCF.

C Program to Find LCM and HCF of two numbers

#include <stdio.h>

int main() 
{
    int num1, num2, min, max, r, lcm , hcf;
    
    //ask user to enter both the numbers 
    printf("Enter two numbers (eg 12 5): ");
    scanf("%d %d", &num1, &num2);
    
    //compare both the number
    //find out maximum and minimum number
    if(num1>num2)
    {
    	max= num1;
    	min= num2;
	}
	else if(num2> num1)
	{
		max= num2;
		min = num1;
	}
	
	//if both the numbers are same
	//both the numbers are the HCF itself
	if(num1==num2)
	{
		hcf=num1;
	}
	//if numbers are not same
	else
	{
		do
		{
			//find the remainder
			r = max%min;
			//now set the divisor to maximum
			//and remainder to minimum
			max= min;
			min=r;
		}while(r!=0);  //keep looping until remainder become 0
		hcf = max;
	}
	
	lcm = (num1*num2)/hcf;
	printf("The HCF of %d %d is %d\n", num1, num2, hcf);
	
	printf("The LCM of %d %d is %d", num1, num2, lcm);
	return 0;
}

Output

Enter two numbers (eg 12 5): 10 3
The HCF of 10 3 is 1
The LCM of 10 3 is 30

C++ Program to Find LCM and HCF of two numbers

#include <iostream>
using namespace std;

int main() 
{
     int num1, num2, min, max, r, lcm , hcf;
    
    //ask user to enter both the numbers 
    cout<<"Enter two numbers (eg 12 5): "; cin>>num1>> num2;
    
    //compare both the number
    //find out maximum and minimum number
    if(num1>num2)
    {
    	max= num1;
    	min= num2;
	}
	else if(num2> num1)
	{
		max= num2;
		min = num1;
	}
	
	//if both the numbers are same
	//both the numbers are the HCF itself
	if(num1==num2)
	{
		hcf=num1;
	}
	//if numbers are not same
	else
	{
		do
		{
			//find the remainder
			r = max%min;
			//now set the divisor to maximum
			//and remainder to minimum
			max= min;
			min=r;
		}while(r!=0);  //keep looping until remainder become 0
		hcf = max;
	}
	
	lcm = (num1*num2)/hcf;
	cout<<"The HCF of "<< num1<<" "<< num2<<" is "<< hcf<<endl;
	
	cout<<"The LCM of "<<num1 <<" "<<num2<<" is " <<lcm;
        return 0;
}

Output

Enter two numbers (eg 12 5): 500 7
The HCF of 500 7 is 1
The LCM of 500 7 is 3500

Python Program to Find LCM and HCF of two numbers

num1, num2 = map(int, input("Enter two numbers (eg 12 5): ").split())
# if both the numbers are same
# both the numbers are the HCF itself
if num1==num2:
    hcf = num1
    lcm = num1

# if numbers are not same
else:
    # find out maximum and minimum number
    maxi = max(num1, num2)
    mini = min(num1, num2)

    if maxi%mini ==0:
        hcf = mini
    else:
        while(maxi%mini):
            # find the remainder
            # set the divisor to maximum
            # and remainder to minimum
            r= maxi%mini
            maxi = mini
            mini = r
        hcf = mini
        lcm = (num1*num2)//hcf

print(f"The HCF of {num1} {num2} is:",hcf )
print(f"The LCM of {num1} {num2} is:", lcm)

Output

Enter two numbers (eg 12 5): 320 128
The HCF of 320 128 is: 64
The LCM of 320 128 is: 640

Conclusion

In this programming article, you learned how to find the HCF and LCM of two numbers in 3 different programming languages. Finding LCM and HCF is also one of the most common interview questions. Carefully read and implement the above program of your own so that you won't get confused in the interview.

If you like the above article and have any suggestions or queries, feel free to let us know by commenting down below.

People are also reading:

• Find ancestors of a given node in a Binary Tree
• Diameter of a Binary Tree
• Subset Sum Problem
• Bottom View of a Binary Tree
• Clone a Singly Linked List
• Reverse a Linked List
• Maximum size square sub-matrices with all 1’s
• Longest Increasing Subsequence using Dynamic Programming
• Merge Sort for Linked Lists
• Convert a Binary Tree to Doubly Linked List