Authors:
Stuart Reges, Marty Stepp
Chapter:
Program Logic And Indefinite Loops
Exercise:
Exercises
Question:2 | ISBN:9780136091813 | Edition: 2
Question
Write a method called gcd that accepts two integers as parameters and returns the greatest common divisor (GCD) of the two numbers. The GCD of two integers a and b is the largest integer that is a factor of both a and b.
One efficient way to compute the GCD of two numbers is to use Euclid’s algorithm, which states the following:
GCD (a, b) = GCD (b, a % b)
GCD (a, 0) =Absolute value of a
Answer
import java.util.Scanner;
public class GCDOfTwoNumbers {
// recursive funtion to find the gcd of two numbers
public int GCD(int value1, int value2) {
// using euclid algorithm
// GCD (a, b) = GCD (b, a % b)
// GCD (a, 0) = return a
//
if (value2 == 0)
return value1;
// we recursion to call the funtion in loop
return GCD(value2, value1 % value2);
}
// main method
public static void main(String args[]) {
Scanner input = new Scanner(System.in);
System.out.println("enter two positive integers: ");
int value1 = input.nextInt();
int value2 = input.nextInt();
GCDOfTwoNumbers gcdOf = new GCDOfTwoNumbers();
int gcd = gcdOf.GCD(value1, value2);
System.out.println("GCD of " + value1 + "," + value2 + " is: " + gcd);
input.close();
}
}
Output:
enter two positive integers:
8
12
GCD of 8,12 is: 4