java program to find gcd of two numbers

Greatest common divisor program in java

The greatest common divisor for 2 number is that the largest number that completely divides both.

For example, the GCD of 16, 24 is 8 that is the highest value that completely divides both 16 and 24. GCD is also reffered to HCF (highest common factor).

We'll use Euclid's algorithm to find the GCD of a and b.

Euclid's algorithm

According to Euclid's algorithm, if a = bq + r (q = quotient, r = remainder, after dividing a by b) and if r is 0 then

gcd(a,b) = b

otherwise,

gcd(a, b) = gcd(b, r)

To understand why is that so, assume that d is the number which divides a and b. 

It means that it can also divide a - bq (directly saying r). 

So you can pretty much understand that d is the factor of a, b as well as r. 

Instead of calculating the gcd(a, b), we can also calculate the gcd(b, r) which has the similar answer as gcd(a, b).

Euclid's algorithm flowchart

let's figure out the gcd of 50 and 60 using Euclid's algorithm 

1) a = 50, b = 60 --> (50 = 60 X 0+ 50)

r = a mod b = 50

gcd(a, b) = gcd(b, r) = gcd(60, 50), since r is not 0

2) a = 60, b = 50 --> (60 = 50 X 1 + 10)

r = a mod b = 10

gcd(a, b) = gcd(b, r) = gcd(50, 10), again r is not 0

3) a = 50, b = 10 --> (50 = 10 X 5 + 0)

r = a mod b = 0

gcd(r, r1) = r1, now r is 0.

4) answer = 10.

Java program to find gcd of two numbers without recursion

  
      import java.util.Scanner;
      
      class Main {
      
          public static void main(String[] args) {
      
              System.out.println("Enter the two numbers:
                  "); Scanner scan = new Scanner(System.in);
      
                  int m = scan.nextInt();
      
                  int n =
                  scan.nextInt();
      
                  System.out.println("Gcd: " + gcd(m, n));
      
              }
      
              private static int gcd(int m, int n) {
      
                  int r = m % n;
      
                  while (r != 0) {
      
                      m = n;
                      n = r;
      
                      r = m % n;
      
                  }
      
                  return n;
              }
          }
        

Program output

Enter the two numbers:
      16 24
      Gcd: 8
      

Other Recommended Posts

• Java program to find the area of a triangle
• java program to find factorial
• java game development

Java program to find the greatest common divisor of two numbers using recursion

           import java.util.Scanner;
       class Main {
           public static void main(String[] args) {
               System.out.println("Enter the two
                   numbers: ");
      
                   Scanner scan = new Scanner(System.in);
      
                   int m =
                   scan.nextInt();
      
                   int n =
                   scan.nextInt();
      
                   scan.close();
      
                   System.out.println("Gcd: " + gcd(m,
                       n));
      
               }
      
               private static int
               gcd(int a, int b) {
      
                   int r = a %
                       b;
      
                   if (r ==
                       0) return b;
      
                   return
                   gcd(b, r);
      
               }
      
           }
          

Program output

            Enter the two numbers:
            20 15
            Gcd: 5