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

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实现欧几里得算法（递归）

//欧几里得算法实现 publicstatic 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)); } }//欧几里得算法实现（递归） publicstatic int gcd(int a,int b) { if(b==0) return a; int temp; temp = a%b; a =b; b=temp; return gcd(a,b); } }