如何验证最大公约数

Question

求两个正整数的最大公约数，大致算法如下：如果a>b 则a=kb+r  其中r就是a除以b得到的余数，调用fun（a，b）如果r等于0的话，则b就是a，b的最大公约数，如果r不等0，则以fun（b，r）递归调用方法，直到r=0,最后的a就是最大公约数现在我们应该怎么来验证这个算法是正确的呢？
我的一个方法是通过一个循环，从大的数a开始向小的数b递减操作，当这个数r能够同时被a，b整除时，r就是a，b的最大公约数，不知道对不对，还有其他的验证方法吗，谢谢！

Answer 1

public class Test{
        public static void main(String[] args){
                System.out.println(fun(36,24));
        }
        static int fun(int a,int b){
                int r=a%b;
                if(r==0) return b;
                return fun(b,r);
        }
}题目已经给出了最佳的算法了,你还要自己一个一个的除?虽然是递归的效率不高,也比一个一个的除效率高.

Answer 2

fun应该再检测一下,a是否大于b.如果a<b没有最大公约数.

Answer 3

如果你调用fun(24,36) 结果是一样的 只是多了一次递归，第一次递归正好调整成fun(36,24) 我挺佩服这算法的发明者的。

Answer 4

如果你是说想通过代码验证，那么你可以计算出最大公约数r之后
for(int i = r + 1; i <= b; i++)
  if(a % i == 0 && b % i == 0)
    System.err.println("算法出错了，还存在公约数" + i);
不过，当然这个算法是没有错的，r一定是最大公约数；如果错误也一定是你计算r的错误

Answer 5

public class Test{
        public static void main(String[] args){
                System.out.println(fun(24,36));
        }
        static int fun(int a,int b){
int r=a%b;
while(r!=0){
a=b;
b=r;
r=a%b;
}
return b;
        }
}非递归算法.没有检测a,b.