Coding Noob - 1 year ago 74
Java Question

# How to write a Java function to implement Euclid's algorithm for computing the greatest common divisor gcd(m, n)

I need to edit the main function to compute (m,n) for all m and n between 2 and 10, but I am not sure how to do so.

I need to write a Java function to implement Euclid's algorithm for computing the greatest common divisor gcd(m, n), which is the largest integer k dividing both m and n.

When the loop stops, the gcd is in m. Add the gcd() function to the NumericFunctions class and include code in main() to compute gcd(m, n) for all m and n between 2 and 10.

Source code:

``````public class NumericFunctions {

public static long factorial(int n) {

long result = 1;

for (int i = 2; i <= n; i++) {

result *= i;
}
return result;
}

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

if ((m % n) == 0)

return n;

else

return gcd(n, m % n);
}

public static void main(String[] args) {

for (int n = 1; n <= 10; n++)

for (int m = 1; m <= 10; m++){

System.out.println(gcd(n,m));

System.out.println(" ");

}
}
``````

There was an infinite recursion in your `gcd()` function (`gcd(2, 1);` for example). So, change your function for something like this

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

if (m > n) {
if ((m % n) == 0)
return n;
else
return gcd(n, m % n);
}
else {
if ((n % m) == 0)
return m;
else
return gcd(m, n % m);
}
}

public static void main(String[] args) {

for (int n = 1; n <= 10; n++) {

for (int m = 1; m <= 10; m++) {
System.out.println("n: " + n + " m: " + m + " gcd: " + gcd(n, m));
}
}
}
``````
Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download