java程序:求三个数的最大公约数和最小公倍数

2023-02-18 00:00:00 个数 最小公倍数 最大公约数

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

/*
 *main方法用于测试结果
 *
 */

public class GreatestCommonDivisor {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int a = sc.nextInt();
        int b = sc.nextInt();
        int c = sc.nextInt();
        int max_gcd1 = maxGcd1(a, b, c);
        System.out.println("最大公约数:"+max_gcd1);
        int max_gcd2 = maxGcd2(a, b, c);
        System.out.println("最大公约数:"+max_gcd2);
        int max_gcd3 = maxGcd3(a, b, c);
        System.out.println("最大公约数:"+max_gcd3);
        int min_gbs = mingbs1(a, b, c);
        System.out.println("最小公倍数:"+min_gbs);
    }
/*
* 短除法:三者共同除以一个数,除至没有余数为止
* 将所得值乘起来
* 就可以得到相应的最大公约数
* */
public static int maxGcd1(int a, int b, int c) {
    List<Integer> l = new ArrayList<Integer>();
    int max_Gcd = 1;
    for (int i = 1; i < Math.max(Math.max(a, b), c); i++) {
        if (a % i == 0 && b % i == 0 && c % i == 0) {
            l.add(i);
        }
    }
    for (Integer integer : l) {
        max_Gcd = 1;
        max_Gcd *= integer;
    }
    return max_Gcd;
}

/**
 * (1)用a除以b(a≥b),得 余数r1 。
 * <p>
 * (2)若 r1=0 ,则(a,b)=b  ;
 * (3)若  r1!=0,则再用b除以 r1 ,得 余数r2 .
 * (4)若 r2=0 ,则(a,b)=r2  ;若 r2!=0 ,则继续用  r1除以r2  ,......,如此下去,直到能整除为止。
 * 其最后一个余数为0的除数即为  的最大公约数。
 */
public static int maxGcd4(int a, int b) {
    int i = a % b;
    int max_gcd = 1;
    if (i == 0) {
        max_gcd = b;
        //System.out.println(max_gcd);
    } else {
        a = b;
        b = i;
        max_gcd = maxGcd4(a, b);
    }
    return max_gcd;

}
/*
 * 三个数用辗转相除法求最大公约数:
 * 如两个数求最大公约数一样
 * 将两个数的最大公约数求出来,与第三个在进行一次辗转相除法
 *
 */

public static int maxGcd2(int a, int b, int c) {
    int d = maxGcd4(a, b);
    int i = c % d;
    int max_gcd = 1;
    if (i == 0) {
        max_gcd = d;
        // System.out.println(max_gcd);
    } else {
        c = maxGcd4(a, b);
        d = i;
        max_gcd = maxGcd4(c, d);
    }
    return max_gcd;
}

/*
 * 三个数用更相减损法求最大公约数
 *先将两个数的最大公约数求出来
 * 再把公约数与第三个数进行一次更相减损法
 */
public static int maxGcd3(int a, int b, int c) {
    int loop = 0;
    int max_gcd = 1;
    int h = maxGcd5(a, b);
    while (a % 2 == 0 && h % 2 == 0) {
        a = a / 2;
        h = h / 2;
        loop++;
        break;
    }
    int g, d, e;
    g = Math.max(a, b);
    d = Math.min(a, b);
    while (true) {
        e = g - d;
        if (e == d) {
            break;
        } else {
            g = Math.max(d, e);
            d = Math.min(d, e);
        }
    }
    if (loop == 0) {
        max_gcd = e;
    } else {
        max_gcd = e * 2 * loop;
    }
    return max_gcd;
}
/*
 * 更相减损法:第一步:任意给定两个正整数;判断它们是否都是偶数。若是,则用2约简;若不是则执行第二步。
 * 第二步:以较大的数减较小的数,接着把所得的差与较小的数比较,并以大数减小数。继续这个操作,直到所得的减数和差相等为止。
 *
 */
public static int maxGcd5(int a, int b) {
    int loop = 0;
    int max_gcd = 1;
    while (a % 2 == 0 && b % 2 == 0) {
        a = a / 2;
        b = b / 2;
        loop++;
        break;
    }
    int c, d, e;
    c = Math.max(a, b);
    d = Math.min(a, b);
    while (true) {
        e = c - d;
        if (e == d) {
            break;
        } else {
            c = Math.max(d, e);
            d = Math.min(d, e);
        }
    }
    if (loop == 0) {
        max_gcd = e;
    } else {
        max_gcd = e * 2 * loop;
    }
    return max_gcd;
}
/**
 * 1.把三个数除以最大公因数
 * 2.然后把两个数的公约数除去,直到两个数互为质数为止
 * 3.把所得数字乘起来即为最小公倍数
 */

public static int mingbs1(int a, int b, int c) {
    int max_gcd = maxGcd1(a, b, c);
    int mingbs = 1;
    a /= max_gcd;
    b /= max_gcd;
    c /= max_gcd;
    int m = maxGcd4(a, b);
    int k = maxGcd4(a, c);
    int l = maxGcd4(b, c);
    if (m != 1) {
        a /= m;
        b /= m;
        mingbs = a * b * c * m * max_gcd;
    } else if (k != 1) {
        a /= k;
        c /= k;
        mingbs = a * b * c * k * max_gcd;
    } else if (l != 1) {
        b /= l;
        c /= l;
        mingbs = a * b * c * l * max_gcd;
    } else if (m == 1 && k == 1 && l == 1) {
        mingbs = a * b * c * max_gcd;
    }
    return mingbs;
}

}
欢迎各位大牛指点

    原文作者:诗洋丶
    原文地址: https://blog.csdn.net/qq_37233149/article/details/82502384
    本文转自网络文章,转载此文章仅为分享知识,如有侵权,请联系博主进行删除。

相关文章