1.欧几里得算法
可求两个正整数的最大公约数。
计算公式为gcd(a, b) = gcd(b, a % b）。
证明该算法就是证明gcd(a, b) = gcd(b, a % b），
证明过程如下：
1.设有两个正整数a，b。 有a=kb+r.（a>b）。
2.设d为a和b的任意一个公约数，记为d|a,d|b(就是d可以整除a，d可以整除b)。
3.有r=a-kb.所以r也可以被d整除，d|r。
4.所以(a,b)和(b,a%b)的公约数是一样的，即gcd(a, b) = gcd(b, a % b);所以(b,a%b)的最大公约数就是(a,b)的最大公约数。
2.java实现欧几里得算法（递归）
//欧几里得算法实现
public static int gcd(int a,int b) {
if(b==0)
return a;
int temp;
temp = a%b;
a =b;
b=temp;
return gcd(a,b);
}
}
3.java实现求两个正整数最大公约数
import java.util.Scanner;
//greatest common divisor最大公约数，欧几里得算法实现。
public class Gcd {
public static void main(String[] args) {
int a=0,b=0;
System.out.println("请输入两个正整数来求其最大公约数");
Scanner scanner = new Scanner(System.in);
a = scanner.nextInt();
b = scanner.nextInt();
if(a<=0 || b<=0) {
System.out.println("输入错误！");
}else {
System.out.println("最大公约数为："+gcd(a,b));
}
}
//欧几里得算法实现（递归）
public static int gcd(int a,int b) {
if(b==0)
return a;
int temp;
temp = a%b;
a =b;
b=temp;
return gcd(a,b);
}
}
