Table of Contents
In this post, we will see how to find Greatest common divisor(GCD) and Least Common Multiple(LCM) in java.
GCD is calculated using Euclidean algorithm and LCM is calculated using reduction by GCD
When you run above program, you will get following output:
GCD is calculated using Euclidean algorithm and LCM is calculated using reduction by GCD
Eucid algo for calculating GCD is:
Lets say , there are two numbers , a and b so
GCD of two numbers = GCD (b,a%b) and GCD(a,0)=a
LCM can be calculated using reduction by GCD :
LCM of two numbers a and b = a * b/GCD(a,b)
Java program :
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 |
package org.arpit.java2blog; import java.util.Scanner; public class GCDLCMMain { /** * @author arpit mandliya */ public static void main(String[] args) { Scanner input = new Scanner(System.in); System.out.println("Enter the two numbers: "); int number1 = input.nextInt(); int number2 = input.nextInt(); System.out.println("The GCD of two numbers is: " + gcd(number1, number2)); System.out.println("The LCM of two numbers is: " + lcm(number1, number2)); input.close(); } // Using Eucid algorithm for calculating gcd public static int gcd(int a,int b) { if(b==0) return a; else return gcd(b,a%b); } public static int lcm(int a,int b) { return a*b/(gcd(a,b)); } } |
|
1 2 3 4 5 6 7 |
Enter the two numbers: 4 6 The GCD of two numbers is: 2 The LCM of two numbers is: 12 |
Was this post helpful?
Let us know if this post was helpful. Feedbacks are monitored on daily basis. Please do provide feedback as that\'s the only way to improve.
