美文网首页
求两个数的最大公约数

求两个数的最大公约数

作者: 顶儿响叮当 | 来源:发表于2016-03-14 10:52 被阅读17次

    **假设把x和y的最大公约数表示成为f(x,y)
    f(x,y) = f(y,x%y) **

    /* 用欧几里德算法求最大公约数 
     * 求最大公约数是一个比较基础的问题, 
     * 欧几里得早在《几何原本》中就阐明了一个高效的算法, 
     * 据说这大概发生在公元前300年左右。 
     * 具体是这样的:假设把x和y的最大公约数表示成为f(x,y), 
     * 并且x>=y>0。现在取k=x/y,b=x%y,则x=k*y+b, 
     * 变形为b=x - k*y;x和y能被f(x,y)整除,那么b也能被f(x,y)整除; 
     * 所以 f(x,y) = f(y,x%y) 
     */  
    
    int GCD(int x,int y)  
    {  
        return (!y) ? x : GCD(y,x%y);  
    } 
    
    

    相关文章

      网友评论

          本文标题:求两个数的最大公约数

          本文链接:https://www.haomeiwen.com/subject/ursflttx.html