[编程入门]最大公约数与最小公倍数-题解（Java代码）

·知识&&分析：
更相减损术求两个数的最大公约数 ：之前大的数 =（赋值） |两数差|（绝对值符号） ，直到两个数相等为止；所得的即为最大公因数利用各个数值之间的关
系求最小公倍数和最大公因数。同时：还可以运用更相减损术和辗转相除法，亦或短除法（比较简单）。
下面的代码（1）则是使用最初始的办法：
                       1：分解质因数
                       2：求公因数
                        （1）：找到最大公因数
                        （2）：用两数的积来除以公因数（每个公因数最多用两次）
                        （3）：在（2）中，为了能够辨别是否已经，在求最小公倍数之前还要设置一个相应的布尔类型的数组
代码（2）则是短除法利用方法（1）和方法（2）还可以求出处最大的公有质因数
代码（4）是使用的更相减损术（较简单）
·最大公因数 = 公有的质因数的积
·在使用方法3时，应该明确知道：
                             1）最大公因数 * 最大公因数 * 短除后的余数1 * 余数2 = 两数积
                             2）最小公倍数 = 最大公因数 * 短处后的余数1 * 余数2
                       因而有：最小公倍数 = 最大公因数除两数的积

·以下的方法一个比一个简单，但是知识量越来越大，由下而上，步骤越详细
·显然，更相减损术的（4），（3）是最简单的，但是（1）是使用的技巧最多的

参考代码:

（1）
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		int[] array;
		byte[] ij = new byte[]{0,0};
		array = new int[2];
		int[][] cFactor = new int[2][10];
		boolean[] b = new boolean[10];                //用来判断下面的内层的相应的公质因数是否已经被用过
		array[0] = scanner.nextInt();
		array[1] = scanner.nextInt();
		int[] x = new int[] {array[0],array[1]};
		x[1] *= x[0];
		x[0] = 1;
		for(byte i = 0;i < 2;i++) {                 //分解质因数        
			for(byte j = 2;array[i] != 1;) {
				if(array[i]%j == 0) {
					cFactor[i][ij[i]] = j;
					array[i] /= j;
					ij[i]++;
					j = 2;
				}
				else {
					j++;
				}
			}
		}

		for(byte m = 0;m < ij[0];m++) {                //获取公因数
			for(byte n = 0;n < ij[1];n++) {
				if(cFactor[0][m]==cFactor[1][n] && (!b[n])) {   //关键点
					b[n] = true; 
					x[0] *=cFactor[0][m];
					x[1] /= cFactor[0][m];
				}
			}
		}
		System.out.println(x[0] +" "+ x[1]);
		
	}
}
```
（2）//短除法
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		int[] array;
		int counter = 0;
		array = new int[] {1,1,1};
		int[] cFactor = new int[10];
		array[0] = scanner.nextInt();
		array[1] = scanner.nextInt();
		for(byte i = 2;i = i ;) {           
			if(array[0] % i == 0 && array[1] % i == 0){
				cFactor[counter] = i;
				counter ++;
				array[0] /= i;
				array[1] /= i;
				i = 2;
			}
			else {
				i++;
			}
		}
		for(byte i = 0;i < counter;i++) {
			array[2] *= cFactor[i];
			array[0]*=cFactor[i];
		}
		System.out.print(array[2] + " " + array[0] * array[1]);
	}
}
```
(3):
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		int[] array;
		array = new int[2];
		array[0] = scanner.nextInt();
		array[1] = scanner.nextInt();
		if(array[0] < array[1]) {
			int t = array[0];
			array[0] = array[1];
			array[1] = t;
		}
		for(int i = array[1];i > 0;i--) {
		    if(array[0] % i == 0&&array[1]%i == 0) {
			System.out.print(i + " " + array[0] * array[1] / i);
			break;
			}
		}
	}
}
```
（4）：
import java.util.Scanner;
import java.util.Arrays;                     //java数组头文件

public class Main {
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		int[] array;
		array = new int[2];
		array[0] = scanner.nextInt();
		array[1] = scanner.nextInt();
		int x = array[0] * array[1];         //积 = 最大公约数 * 最小公倍数
		Arrays.sort(array);
		while(array[0] != array[1]) {          //循环相见求最大公约数
			array[1] = array[1] - array[0];
			Arrays.sort(array);             //位于Arrays中，排序方法是从默认从小到大
		}
		System.out.print(array[0] + " " + x / array[0]);
	}	
}