ITLife365 生活 互动学习空间 - 互动学习空间

package com.common.main;
public class Gongys {
    /** 求两个数的最大公约数
     * @author happymen001
     * @version Jun 19, 2010  12:24:45 AM
     * @param args
     * @return void
     */
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Gongys gcd = new Gongys ();
        int m = gcd.Gcd(5767,4453);
        System.out.println(m);
    }
    /**
    辗转相除法．
　　当两个数都较大时，采用辗转相除法比较方便．其方法是：
　　以小数除大数，如果能整除，那么小数就是所求的最大公约数．否则就用余数来除刚才的除数；再用这新除法的余数去除刚才的余数．依此类推，直到一个除法能够整除，这时作为除数的数就是所求的最大公约数．
　　例如：求4453和5767的最大公约数时，可作如下除法．
　　5767÷4453＝1余1314
　　4453÷1314＝3余511
　　1314÷511＝2余292
　　511÷292＝1余219
　　292÷219＝1余73
　　219÷73＝3
　　于是得知，5767和4453的最大公约数是73．
　　辗转相除法适用比较广，比短除法要好得多，它能保证求出任意两个数的最大公约数．
     */
    /**
     * @author happymen001
     * @version Jun 19, 2010  2:11:07 PM
     * @param num1
     * @param num2
     * @return
     * @return int
     */
    private static int Gcd(int num1,int num2){
        int gcd = 0;
        if(num1 == num2){
            gcd = num1;
        }
        if(num1 > num2 ){
            int temp = 0;
            temp = num2 ;
            num2 = num1;
            num1 = temp ;
        }
        if(num2 % num1 ==0){
            gcd = num1;
        }else {
            int temp = num1;
            num1 = num2 % num1 ;
            num2 = temp ;
            gcd  =Gcd(num1,num2);
            
        }
        return gcd;
    }
    
    }
//http://blog.csdn.net/dspingk/archive/2010/02/20/5312976.aspx