1.歐幾里得算法
可求兩個正整數(shù)的最大公約數(shù)延塑。
計算公式為gcd(a, b) = gcd(b, a % b）扭弧。
證明該算法就是證明gcd(a, b) = gcd(b, a % b），
證明過程如下：
1.設有兩個正整數(shù)a，b芦劣。 有a=kb+r.（a>b）。
2.設d為a和b的任意一個公約數(shù)说榆，記為d|a,d|b(就是d可以整除a虚吟，d可以整除b)。
3.有r=a-kb.所以r也可以被d整除签财，d|r串慰。
4.所以(a,b)和(b,a%b)的公約數(shù)是一樣的，即gcd(a, b) = gcd(b, a % b);所以(b,a%b)的最大公約數(shù)就是(a,b)的最大公約數(shù)唱蒸。
2.java實現(xiàn)歐幾里得算法（遞歸）
//歐幾里得算法實現(xiàn)
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實現(xiàn)求兩個正整數(shù)最大公約數(shù)
import java.util.Scanner;
//greatest common divisor最大公約數(shù)邦鲫，歐幾里得算法實現(xiàn)。
public class Gcd {
public static void main(String[] args) {
int a=0,b=0;
System.out.println("請輸入兩個正整數(shù)來求其最大公約數(shù)");
Scanner scanner = new Scanner(System.in);
a = scanner.nextInt();
b = scanner.nextInt();
if(a<=0 || b<=0) {
System.out.println("輸入錯誤神汹！");
}else {
System.out.println("最大公約數(shù)為："+gcd(a,b));
}
}
//歐幾里得算法實現(xiàn)（遞歸）
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);
}
}
