JAVA program to find lcm and gcd/hcf of two numbers

JAVA program to find lcm and gcd/hcf of two numbers

This JAVA program is to find LCM and GCD/HCF of two numbers.

LCM(Least Common Multiple) is the smallest positive number which is divisble by both the numbers.

For example, lcm of 8 and 12 is 24 as 24 is divisble by both 8(8*3) and 12(12*2).

HCF(Highest Common Factor)/GCD(Greatest Common Divisor) is the largest positive integer which divides each of the two numbers.

For example, gcd of 8 and 12 is 4 as divisors of 8 are 1,2,4,8 and divisors of 12 are 1,2,3,4,12 , so the greatest common divisor is 4.

Logic

GCD would be clearly understood by the the dry run.As we know that lcm is nothing but multiplication of both the numbers divided by the gcd of the two numbers.

Dry Run of the Program

Take input ‘n1’  ‘n2’ .Let us take n1=4 and n2=6

if (n1>n2)  i.e. if(4>6)  false so we do not execute the if statements.

else {

numerator=n2; i.e. numerator=6;

denominator=n1; i.e. denominator=4;

}

remainder=numerator%denominator;  i.e.  remainder=6%4; hence remainder=2

1st iteration while(remainder!=0)  i.e.  while(2!=0)

numerator=denominator;   i.e. numerator=4;

denominator=remainder;  i.e. denominator=2;

remainder=numerator%denominator;  i.e. remainder=4%2; hence  remainder=0;

We exit the while loop as remainder=0.

gcd=denominator;  hence gcd=2

lcm=n1*n2/gcd;  i.e. lcm=4*6/2  hence lcm=12

We have found the gcd and lcm of the two numbers.

Program

import java.util.*;
 
class lcmGCD
{
	public static void main(String args[])
	{
	    	int n1,n2;
	    	int gcd,lcm,remainder,numerator,denominator;
 		Scanner sc = new Scanner(System.in);
	    	System.out.println("Enter two Numbers");
	    	n1=sc.nextInt();
		n2=sc.nextInt();
	    	if (n1>n2)
		{	
        		numerator=n1;
        		denominator=n2;
    		}
    		else
    		{
       			numerator=n2;
       		 	denominator=n1;
	    	}
	    	remainder=numerator%denominator;
    		while(remainder!=0)
    		{
    	   		numerator=denominator;
   		     	denominator=remainder;
       		 	remainder=numerator%denominator;
    		}
    		gcd = denominator;
    		lcm = n1*n2/gcd;
    		System.out.println("GCD of "+n1+" and "+n2+" = "+gcd);
    		System.out.println("LCM of "+n1+" and "+n2+" = "+lcm);
	}
}

Output

Share Me!