(Intro to java class help?) Write a static method named gcd that accepts two int
ID: 3724333 • Letter: #
Question
(Intro to java class help?) Write a static method named gcd that accepts two integers as parameters and returns the greatest common divisor (GCD) of the two numbers. The greatest common divisor of two integers a and b is the largest integer that is a factor of both a and b. The GCD of any number and 1 is 1, and the GCD of any number and 0 is that number. One efficient way to compute the GCD is to use Euclid's algorithm, which states the following:
GCD(a, b) = GCD(b, a % b)
GCD(a, 0) = Absolute value of a
For example, gcd(24, 84) returns 12, gcd(105, 45) returns 15, and gcd(0, 8) returns 8.
Test your code with the following code file:
public class TestGCD {
public static void main(String[] args) {
System.out.println("GCD of 27 and 6 is " + gcd(27, 6)); // 3
System.out.println("GCD of 24 and 84 is " + gcd(24, 84)); // 12
System.out.println("GCD of 38 and 7 is " + gcd(38, 7)); // 1
System.out.println("GCD of 45 and 105 is " + gcd(45, 105)); // 15
System.out.println("GCD of 1 and 25 is " + gcd(1, 25)); // 1
System.out.println("GCD of 25 and 1 is " + gcd(25, 1)); // 1
System.out.println("GCD of 0 and 14 is " + gcd(0, 14)); // 14
System.out.println("GCD of 14 and 0 is " + gcd(14, 0)); // 14
}
// your code goes here
}
Explanation / Answer
public class TestGCD {
public static void main(String[] args) {
System.out.println("GCD of 27 and 6 is " + gcd(27, 6)); // 3
System.out.println("GCD of 24 and 84 is " + gcd(24, 84)); // 12
System.out.println("GCD of 38 and 7 is " + gcd(38, 7)); // 1
System.out.println("GCD of 45 and 105 is " + gcd(45, 105)); // 15
System.out.println("GCD of 1 and 25 is " + gcd(1, 25)); // 1
System.out.println("GCD of 25 and 1 is " + gcd(25, 1)); // 1
System.out.println("GCD of 0 and 14 is " + gcd(0, 14)); // 14
System.out.println("GCD of 14 and 0 is " + gcd(14, 0)); // 14
}
public static int gcd(int n1, int n2){
// Gcd of 0 and number is number
if (n1 == 0)
return n2;
if(n2==0)
return n1;
// base condition
if (n1 == n2)
return n1;
// n1>n2 case
if (n1 > n2)
return gcd(n1-n2, n2);
// n2>n1 case
return gcd(n1, n2-n1);
}
}
/*
sample output
GCD of 27 and 6 is 3
GCD of 24 and 84 is 12
GCD of 38 and 7 is 1
GCD of 45 and 105 is 15
GCD of 1 and 25 is 1
GCD of 25 and 1 is 1
GCD of 0 and 14 is 14
GCD of 14 and 0 is 14
*/
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.