How to find Greatest Common Divisor in Java

In this post I am going  to present an efficient algorithm for finding the greatest common divisor between two integers using recursion.

The greatest common divisor of two integers is the largest number that can properly divide both numbers. The program ask for two input parameter and then then calculate the greatest common divisor recursively.


GreatestCommonDivisor.java

import java.util.Scanner;

public class GreatestCommonDivisor {

       /** Find gcd for integers m and n */

       public static int gcd(int m, int n) {

              if (m % n == 0) {

                     return n;

              } else {

                     return gcd(n, m % n);

              }

       }

       /** Main method */

       public static void main(String[] args) {

              // Create a Scanner

              Scanner input = new Scanner(System.in);

              // Prompt the user to enter two integers

              System.out.print("Enter first integer: ");

              int m = input.nextInt();

              System.out.print("Enter second integer: ");

              int n = input.nextInt();

              System.out.println("The greatest common divisor for " + m + 

                        " and " + n + " is " + gcd(m, n));

       }

}

The output of the program should look like:

    Enter first integer: 525
   Enter second integer: 20
   The greatest common divisor for 525 and 20 is: >> 5