【Java】最大公因数和最小公倍数的算法

川长思鸟来 2023-05-22 08:48 19阅读 0赞

# 1.最大公因数 #

**方法1：**找出两个数里面的最大值，利用循环进行求解；可以说，这种方法没有经过任何的算法，利用的纯数学的方法；

但是要循环遍历其中较大的正整数，如果两个数量都非常大的话，效率是非常低的；

如下：

public static int gcd(int a,int b){
            int max=(a>b)?a:b;
            int result=0;
            for(int i=1;i<max;i++){
                if(a%i==0&&b%i==0){
                    result=i;
                }
            }
            return result;
        }

**方法2：**利用辗转相除法

1.假设有两个数a和b，其中a是不小于b的数，记a被b除的余数为r，r=a%b，再取k=a/b（取整）；

2.可知：a=k\*b+r,那么同时能被a，b整除的数也同时能够r，b整除，这样，能被r，b整除的数也同时能被a，b整除；

3.也就是说，a，b的最大公约数就是b，y的最大公约数，则有f(a,b)=f(b,a%b)，（a>=y>0），这样进行递归计算；

算法如下：

public static int gcd(int a,int b){
            if(b==0){
                return a;
            }
            int r=a%b;
            return gcd2(b,r);
        }

# 2.最小公倍数 #

**方法1：**传统的算法，最小公倍数的本质就是在他们之中找到最大的数，然后每次+1，直到找到这样的数同时满足整除两个数的就是最小公倍数；

代码如下：

public static int lcm(int a,int b){
            int temp=0;
            if(a<=0||b==0){
                return -1;
            }
            temp=Math.max(a,b);
            while(temp%a!=0||temp%b!=0){
                temp++;
            }
            return temp;
        }

**方法2：**公式法：最小公倍数=a\*b/(两数的最大公因数)

代码如下：

public static int lcm(int a,int b){
            return a*b/gcd(a,b);
        }
     public static int gcd(int a,int b){
            if(b==0){
                return a;
            }
            int r=a%b;
            return gcd(b,r);
        }