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

谙忆

发布于 2021-01-21 10:57:40

1.2K00

代码可运行

文章被收录于专栏：程序编程之旅程序编程之旅

运行总次数：0

代码可运行

辗转相除法，又被称为欧几里德（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;
    }

循环版本：

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;
    }

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

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2016/03/21 ，如有侵权请联系 cloudcommunity@tencent.com 删除

消息队列 CKafka 版