Java Program to find GCD and LCM of Two Numbers Using Euclid’s Algorithm

«
This is a Java Program to find GCD and LCM of Two Numbers Using Euclid’s Algorithm. Euclid’s Algorithmis an algorithm, a step-by-step procedure for performing a calculation according to well-defined rules, and is one of the oldest numerical algorithms in common use.

We divide the two numbers entered by the user and remainder become divisor while previous divisor become dividend now. This process repeat until the remainder become zero and we get the GCD as divisor which gives remainder as zero. LCM is a little trickier, but probably the best approach is reduction by the GCD, which can be similarly iterated.

Here is the source code of the Java Program to find GCD and LCM of Two Numbers Using Euclid’s Algorithm. The Java program is successfully compiled and run on a Windows system. The program output is also shown below.

advertisement
  1. import java.util.Scanner;
  2. public class Euclid
  3. {
  4.     void gcd(long a, long b)
  5.     {
  6.         while (b > 0)
  7.         {
  8.              long temp = b;
  9.              b = a % b; // % is remainder
  10.              a = temp;
  11.         }
  12.         System.out.println("GCD is "+a);
  13.     }
  14.     void lcm(long a, long b)
  15.     {
  16.         long x = a;
  17.         long y = b;
  18.         while (b > 0)
  19.         {
  20.             long temp = b;
  21.             b = a % b; // % is remainder
  22.             a = temp;
  23.         }
  24.         long gcd = a;
  25.         long lcm = (x * (y / gcd));
  26.         System.out.println("LCM is "+ lcm);
  27.     }
  28.     public static void main(String... a)
  29.     {
  30.         Euclid abc = new  Euclid();
  31.         System.out.println("Enter any two numbers to calculate GCD");
  32.         Scanner s = new Scanner(System.in);
  33.         long x = s.nextLong();
  34.         long y = s.nextLong();
  35.         abc.gcd(x, y);
  36.         System.out.println("Enter any two numbers to calculate LCM");
  37.         long l = s.nextLong();
  38.         long m = s.nextLong();
  39.         abc.lcm(l, m);
  40.     }
  41. }

Output:

$ javac Euclid.java
$ java Euclid
 
Enter any two numbers to calculate GCD
6 50
GCD is 2
Enter any two numbers to calculate LCM
11 17
LCM is 187

Sanfoundry Global Education & Learning Series – 1000 Java Programs.

advertisement

Here’s the list of Best Reference Books in Java Programming, Data Structures and Algorithms.

Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!
advertisement
advertisement
advertisement
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He is Linux Kernel Developer & SAN Architect and is passionate about competency developments in these areas. He lives in Bangalore and delivers focused training sessions to IT professionals in Linux Kernel, Linux Debugging, Linux Device Drivers, Linux Networking, Linux Storage, Advanced C Programming, SAN Storage Technologies, SCSI Internals & Storage Protocols such as iSCSI & Fiber Channel. Stay connected with him @ LinkedIn