Shortcut Method to find HCF and LCM:

Shortcut Method to find HCF and LCM:

       Before writing any program first of all we must have a clear idea about problem and how to solve that problem.Then implement the code for that

What is LCM ??
   LCM stands for Least Common Multiple and defined as the Smallest number that is multiple of two or more numbers.
          Ex:Let us consider two numbers such as 8,12
               Smallest number that is multiple of both 8 and 12 is 24.

        Even though there are many numbers that are multiples of both 8 and 12 such as 48,72........24 is the LCM of 8 and 12 since it is the smallest.

           For more about LCM

How to calculate LCM??
         The most common way that is familiar to us is using prime factorization .and division method as follows

so LCM of 8,12 is '2*2*2*3 =24'

Program to find LCM of two numbers:

#include<stdio.h>

void main()

 {

  int max,num1,num2,t1,t2,i,lcm=1;

  printf("\nEnter Numbers:   ");

  scanf("%d %d",&num1,&num2);

  t1=num1;

  t2=num2;  

  while(t1>1 || t2>1)

   {

    max=t1>t2?t1:t2;

    for(i=2;i<=max;i++)

     {

      if(t1%i==0 && t2%i==0)

       {

        lcm*=i;

        t1/=i;

        t2/=i;

        break;

       }      

      if(t1%i==0)

       {

        lcm*=t1;

        t1/=i;

        break;

       }

       if(t2%i==0)

       {

        lcm*=t2;

        t2/=i;

        break;

       }

     }

   }

  printf("LCM of %d and %d is: %d",num1,num2,lcm);

 }

Output:




What is HCF??

     HCF stands for Highest Common Factor,also Known as GCD Greatest Common Divisor defined as the Largest common factor of the given numbers.

If we know the LCM of two Numbers then their HCF is Calculated using the formula

X*Y=LCM(x,y)*HCF(x,y)

HCF(x,y)=(x*y)/LCM(x,y)

int hcf(int x,int y,int lcm)
 {
   return (x*y)/lcm;
 }

Share on Google Plus