欧几里得算法一、干什么用算出最大两个非负整数的最大公约数。虽然小学知识大家概念很清楚但我们这里还是提下能被两个数AB整除的最大整数C就称C是A和B的最大公约数。可以用GCDA,B表示。GCD是Greatest Common Divisor的缩写。二、欧几里得算法的内容欧几里得是快速找出两个数最大公约的一种算法。算法核心思想例如找AB的最大公约数GCDA,B并且AB如果A0那么GCDABGCD0BB如果B0那么DCDABGCDA0A用余数表示AAB*QRQ表示B的几倍R是余数。GCDA,BGCDBR举例说明A12B8由12 8*14根据欧几里得算法得到GCD12,8GCD8,4然后A8B4由8 4*20根据欧几里得算法得到GCD8,4GCD4,0因为A0B0所以GCD4,04以上我们可以得出GCD12,8GCD8,4GCD4,04从上面的例子中我们可以看到欧几里得算法他把一个复杂的问题逐渐简化成了简单问题。这种算法思想就是通常我们说的分治思想Divide and Conquer。三、证明欧几里得思想1.证明GCDA0A我们知道A的最大公约数是AA*00即0除以任何整数都是0因此我们可以说任何数都可以是0的约数。因为A大于0所以GCDA0A同理我们可以证明出GCDB0B。2.证明GCDA,BGCDBR要想证明GCD(A,B)GCD(B,R)首先我们需要证明GCD(A,B)GCD(B,A-B)先上图三个数A,B,C满足A-BC图的左侧说明GCDAB是A和B的最大公约数同时就说明其能整除A和B;可以将其表示为X*GCDABAY*GCDABB得到A-BX*GCDAB-Y*GCDABX-Y*GCDABCGCDAB也是C的一个约数图的中间说明GCDBC是B和C的最大公约数同时就说明其能整除B和C;可以将其表示为M*GCDBCBN*GCDBCC得到BCM*GCDBCN*GCDBCMN*GCDBCAGCDBC也是A的一个约数图的右侧说明GCDAB是B的约数同时也是C的约数算是B和C的一个公共约数但是肯定小于或等于B和C的最大公约数所以GCDABGCDBC;GCDBC是A的约数同时也是B的约数算是A和B的一个公共约数但是肯定小于或等于A和B的最大公约数所以GCDBCGCDAB最终得出GCDABGCDBCGCDBA-B我们证明了GCD(A,B)GCD(B,A-B)接下来我们证明GCD(A,B)GCD(B,R)。GCD(A,B)GCD(B,A-B)可以写成GCD(A,B)GCD(A-B,B)由GCD(A,B)GCD(A-B,B)可以得出GCD(A-B,B)GCD(A-2B,B)以此类推GCD(A,B)GCD(A-B,B)GCD(A-2B,B)GCD(A-3B,B)GCD(A-Q*B,B)因为A可以表示成AQ*BR;将其代入到GCD(A-Q*B,B)中得到GCD(Q*BR-Q*B,B)GCD(R,B)GCD(B,R)进一步得到GCD(A,B)GCD(B,R)