write a java program to find the LCM and greatest common divisor of two numbers
Answers
Answer:
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
java program to find lcm and gcd/hcf of two numbers
Explanation:
Java
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);
}
}