求最大公约数和最小公倍数 - 黑马程序员技术交流社区

/*
* 求最大公约数和最小公倍数
*
* 概念
*
* 最大公约数就是几个数公有的因数中最大的一个
* 假如整数n除以m，结果是无余数的整数，那么我们称m就是n的因数。
* 最小公倍数就是几个数公有的倍数中最小的一个。
* 整数m能够被整数n整除，整数m就是整数n的倍数。
*/
public class Demo2 {
public static void main(String[] args) {
int m = 9;
int n = 4;
System.out.println(最大公约数(m, n));// 调用maxCommonDivisor()方法
System.out.println(最小公倍数(m, n));// 调用minCommonMultiple()方法
}
// 循环法求最大公约数
public static int 最大公约数(int m, int n) {
// 保证m为较大数，n为较小数。若m<n,则进行数据交换
if (m < n) {
int temp = m;
m = n;
n = temp;
}
// 1.若m除以n余数为0，则最大公约数即为较小数n，返回n
// 2.否则，通过交换，将较大数（1中较小数）除以较小数（1中余数），若余数为0，则最大公约数即为较小数，返回n
// 3.否则，通过交换，将较大数（2中较小数）除以较小数（2中余数），。。。。
// 4.直到找到较大数能除尽较小数的时候（顶点为整数1），最大公约数即为那时候的较小数。
while (m % n != 0) {
int temp = m % n;
m = n;
n = temp;
}
// 返回最大公约数
return n;
}
// 求最小公倍数等于两个数中的任一数除以最大公约数，再乘上两个数中另外一个数。
public static int 最小公倍数(int m, int n) {
return m * n / 最大公约数(m, n);
}
}

复制代码

//1.程序分析：利用辗除法。
public class Demo2 {
// 下面的方法是求出最大公约数
public static int gcd(int m, int n) {
while (true) {
// 返回最小公约数
if ((m = m % n) == 0)
return n;
if ((n = n % m) == 0)
return m;
}
}
public static void main(String args[]) throws Exception {
// 取得输入值
// Scanner chin = new Scanner(System.in);
// int a = chin.nextInt(), b = chin.nextInt();
// 例如求a=23,b=32的最小公倍数和最大公约数
int a = 23;
int b = 32;
// 由于main函数是静态的，所以这里的gca也必须是静态的。
int c = gcd(a, b);
System.out.println("最小公倍数：" + a * b / c + "\n最大公约数：" + c);
}
}

复制代码