辗转相除法_欧几里得算法_java的实现（求最大公约数）

辗转相除法，又被称为欧几里德（Euclidean）算法， 是求最大公约数的算法。
当然也可以求最小公倍数。

算法描述

　　两个数a，b的最大公约数记为GCD(a,b)。a，b的最大公约数是两个数的公共素因子的乘积。如462可以分解成2 × 3 × 7 × 11；1071可以分解成3 × 3 × 7 × 17。462和1071的最大公约数等于它们共有的素因数的乘积3 × 7 = 21。如果两数没有公共的素因数，那么它们的最大公约数是1，也即这两个数互素，即GCD(a,b)=1。另g=GCD(a,b)，则a=mg, b=ng，其中m，n均为正整数。由上述分析可知，m，n互素。因为m，n没有公共素因子，GCD(m,n)=1。
　　辗转相除法是一种递归算法。

算法实现：
递归版本：

 private static int gac(int a, int b) { if(a<b){ swap(a,b); } if(b==0) return a; else return gcd(b,a%b); } private static void swap(int a, int b) { a=a^b; b=a^b; a=a^b; }
  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
 

循环版本：

private static int gac(int a, int b) { if(a<b){ swap(a,b); } while(b!=0){ int c = a%b; a=b; b=c; } return a; } private static void swap(int a, int b) { a=a^b; b=a^b; a=a^b; }
  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
 

2个数a,b;已知最大公约数为n；
最小公倍数=a*(b/n);

文章来源: chenhx.blog.csdn.net，作者：谙忆，版权归原作者所有，如需转载，请联系作者。

原文链接：chenhx.blog.csdn.net/article/details/50946397