輾轉相除法求最大公因式

[davidlan]

Method1:
public class Exercise3_1 {
public static void main(String[] args) {
int m = 1000;
int n = 495;
while(n != 0) {
int r = m % n;
System.out.println(m + " % " +n);
m = n;
System.out.println("m = " + m);
n = r;
System.out.println("n = " + n);
}
System.out.printf("最大公因數 %d%n", m);
}
}
--------8<--------8<--------8<--------8<----
1000 % 495
m = 495
n = 10
495 % 10
m = 10
n = 5
10 % 5
m = 5
n = 0
最大公因數 5
-------->8-------->8-------->8-------->8----

[davidlan]

Method2
public class Exercise3_1 {
public static int gcd(int m, int n) {
return n == 0 ? m : gcd(n, m % n);
}
public static int lcm(int m, int n) {
return m * n / gcd(m, n);
}
public static void main(String[] args) {
int p = 1000;
int q = 495;
System.out.printf("gcd(%d, %d) = %d%n", p, q, gcd(p, q));
}
}
--------8<--------8<--------8<--------8<----
gcd(1000, 495) = 5
-------->8-------->8-------->8-------->8----