public class GCD {
static int m, n, temp;
public static void swap() {
if (m < n) {
temp = m;
m = n;
n = temp;
}
}
// 方法一；欧几里得辗转相除法
public static void euclid() {
int count = 1;
for (int r = m % n; r > 0; r = m % n) {
m = n;
n = r;
count++;
}
System.out.println("最大公约数为：" + n);
System.out.println("执行次数为：" + count);
}
// 方法二：Stein算法
public static int stein(int m, int n) {
if (m == 0)
return n;
if (n == 0)
return m;
if (m % 2 == 0 && n % 2 == 0)
return 2 * stein(m >> 1, n >> 1);
else if (m % 2 == 0)
return stein(m >> 1, n);
else if (n % 2 == 0)
return stein(m, n >> 1);
else
return stein((m - n) >> 1, (m + n) >> 1);
}
public static void main(String[] args) {
Scanner s = new Scanner(System.in);
System.out.println("Please enter two numbers:");
m = s.nextInt();
n = s.nextInt();
swap();
euclid();
System.out.println(stein(m, n));
}
}
