Jun 19

Java求两个数的最大公约数

admin , 13:23 , 脚本JQuery » 编程(Java-模式) , 评论(0) , 引用(0) , 阅读(1557) , Via 本站原创 | |
搜索
我已经获得阿里云幸运券,准备分享给您。请点击获取  

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