求最大公约数和最小公倍数

雨点打透心脏的1/2处 2022-06-12 13:25 265阅读 0赞

注：最大公约数和最小公倍数，我都是针对正整数的  
（一）最笨的方法：穷尽法  
2个数的最大公约数的最大值：2数中的较小数。  
2个数的最大公约数的最小值：1  
因此，只在这个范围内进行穷尽。代码示例：

public static int gcd1(int max,int min){
       //穷尽法求最大公约数
            int temp;
            if(max<min){
       //保证max>=min
                temp=max;
                max=min;
                min=temp;
            }
            for(int i=min;i>=1;i--){
                if(max%i==0&&min%i==0){
                    return i;
                }
            }
            return 1;
        }

（二）辗转相除法

1）理解辗转相除法

当余数为0时，终止  
最后1次的除数即是最大公约数，因此最大公约数为6

①被除数=除数\*n+余数，余数=被除数-除数\*n。  
假设最大公约数用gcd来表示，被除数=gcd\*k1,除数=gcd\*k2  
那么，余数=gcd(k1-k2\*n);因此余数一定能被gcd整除  
②每一次递归，使被除数=除数，除数 =余数。使得被除数和除数的数值越来越小，但是这种替换不会影响最终的结果  
③当余数为0时，递归就会结束。这一次的除数即是最大公约数  
2）代码：

/** * 使用递归的方式求最大公约数 * 用min取代max,用max%min取代min,进行下一次递归 * max=min; * min=max%min; * @param max * @param min * @return */
        public static int gcd2(int max,int min){
            int temp;
            if(max<min){
       //保证max>=min
                temp=max;
                max=min;
                min=temp;
            }
            if(max%min==0){
                return min;
            }else{
                return gcd2(min,max%min);
            }
        }

（三）辗转相除的升级版

public static int gcd3(int m,int n){
       //比较费解啊
            while(true){
                if((m=m%n)==0){
                    return n;
                }
                if((n=n%m)==0){
                    return m;
                }
            }
        }

（四）求最小公倍数  
已知2个数正整数m和n，用gcd(m,n)表示这2个数的最大公约数。  
那么m和n的最小公倍数=m\*n/gcd(m,n)。

public static int minCommonMultiple(int m,int n){
            return m*n/gcd(m, n);//求2数的最小公倍数，2数之积/2数的最大公约数
        }