用辗转相除法求三个数的最大公约数和最小公倍数

墨染白筝
  • 147

三个数求最大公约数和求最小公倍数,可否用辗转相除法?
例如:
三个数求最大公约数:
先求前两个数的最大公约数a,然后用a和第三个数再求最大公约数b,得到三个数的最大公约数
三个数求最小公倍数:
先求前两个数的最小公倍数c:(第一个数×第二个数)/a
在用c和第三个数求最小公倍数d:(c 乘 第三个数)/b
得到的d就是三个数的最小公倍数

请问这个方法可行吗?
测试过几个数据,得到的最小公倍数是正确的,但是做题的时候两个测试点只通过了一个,请问有木有反例可举?

题:输入三个数,求他们的最小公倍数
代码:

import java.util.Arrays;  
import java.util.Scanner;  
  
public class Main {  
  
    public static void main(String[] args) {  
  
        Scanner in = new Scanner(System.in);  
        int[] arr = new int[3];  
        for(int i = 0;i<arr.length;i++){  
            arr[i] = in.nextInt();  
        }  
        Arrays.sort(arr);  
        //前两个数的公约数  
        int gy_1 = gy2(arr[0],arr[1]);  
        //三个数的公约数  
        int gy_2 = gy2(gy_1,arr[2]);  
        //开始求前两个数的公倍数  
        int gb_1 = (arr[0]*arr[1])/gy_1;  
        int gb_2 = (gb_1*arr[2])/gy_2;  
        System.out.println(gb_2);  
    }  
    //两个数求最大公约数  
    public static int gy2(int a,int b){  
        if(b==0) return a;  
        return gy2(b,a%b);  
    }  
          
}  
回复
阅读 7.8k
1 个回答

求a, b最小公倍数必须是lcm(a, b) = |a*b| / gcd(a, b),在你的代码中

int gb_2 = (gb_1*arr[2])/gy_2;

int gy_2 = gy2(gy_1,arr[2]);

显然,此时的gy_2并不是gb_1与arr[2]的最大公约数,而是gcd(gy_1, arr[2])。
gb_1是gy_1的倍数,所以gcd(gb_1, arr[2])可以整除gcd(gy_1, arr[2])。当测试样例中gcd(gb_1, arr[2]) != gcd(gy_1, arr[2])时,结果就会错误,比如2 4 8

int gb_1 = a * b / gcd(a, b);
int gb_all = gb_1 * c / gcd(gb_1, c);
private int gcd(int a, int b) {
    if (a < b)
        swap(a, b);
    return (b == 0) ? a : gcd(b, a % b);
}
撰写回答
你尚未登录,登录后可以
  • 和开发者交流问题的细节
  • 关注并接收问题和回答的更新提醒
  • 参与内容的编辑和改进,让解决方法与时俱进
宣传栏