static public int gcd1_1(int x, int y)   
{
  int temp;
  
  do{
  temp = x % y;
  x = y;
  y = temp;
  }while(temp != 0);
  
  return x;
}

辗转相除法

表示不懂~~~

1. 
   
2. public class Test {
   
3. 
   
4.         /**
   
5.          * 最大公约数
   
6.          */
   
7.         public static int gcd1_1(int x, int y) {
   
8.                 int temp;
   
9. 
   
10.                 do {
    
11.                         temp = x % y;
    
12.                         x = y;
    
13.                         y = temp;
    
14.                 } while (temp != 0);
    
15. 
    
16.                 return x;
    
17.         }
    
18. 
    
19.         /**
    
20.          * 上面方法也可以写成下面这种写法
    
21.          */
    
22.         public static int gcd(int x, int y) {
    
23.                 if (x % y == 0) {
    
24.                         return y;
    
25.                 } else {
    
26.                         return gcd(y, x % y);
    
27.                 }
    
28. 
    
29.         }
    
30. 
    
31. }
    
32. 
    
33. /**
    
34. * 分析gcd1_1方法
    
35. * 我们先假设x和y的最大公约数为T
    
36. *
    
37. * 情况1.如果x<y do代码块相当于把x和y的值互换，然后转到下面的情况2：
    
38. *
    
39. * 情况2.如果x>=y，只会有下面两种情况：
    
40. *  ->>2.1 如果x和y的最大公约数T== y的话
    
41. *   那么 x%y=0；返回y即可
    
42. *   
    
43. *  ->>2.2 如果x和y的最大公约数T<y的话 那么x = mT，y=nT （并且m>n）
    
44. *      那么x%y=temp，此时temp一定也是T的整数倍，假设temp=qT，则q一定小于n。此时temp和y的公约数也即是所求的公约数。
    
45. *      如此递归进行2.2步骤，则最终q会越来越小，直至q==1的时候，x%y==0，则此时y的值即为所求最大公约数。
    
46. *
    
47. *
    
48. *
    
49. */
    

复制代码