求最大公约数（欧几里得算法）

package com.itany.oulijide;public class Test{public static void main(String[] args){int result=gcd(50,15);System.out.println(result);}//默认m>n,如果m<n，那么第一次迭代的时候会把两者交换public static int gcd(int m,int n){while(n!=0){int rem=m%n;m=n;n=rem;}return m;}}

运行时间为对数！

其计算原理依赖于下面的定理：

定理：gcd(a,b) = gcd(b,a mod b) (a>b 且a mod b 不为0)

证明：a可以表示成a = kb + r，，则r = a mod b

假设d是a,b的一个公约数，则有

d|a,d|b，而r = a – kb，因此d|r

因此d也是（b,a mod b）的公约数

因此（a,b）和（b,a mod b）的公约数是一样的，其最大公约数也必然相等，得证

的这一半更多地赢取上帝掌握的那一半。