java最大公约数和最小公倍数的关系,java怎么求最大公约数和最小公倍数

Java—最小公倍数和最大公约数

Description
从键盘输入两个正整数，求这两个正整数的最小公倍数和最大公约数，并输出。

Input
输入包括一行。
两个以空格分开的正整数。

Output
两个整数的最小公倍数和最大公约数。

Sample
Input
6 8
Output
24 2

import java.util.Scanner;public class Main {public static void main(String[] args) {// TODO Auto-generated method stubScanner reader = new Scanner(System.in);int n, m, r = 1, temp, a;n = reader.nextInt();m = reader.nextInt();a = n * m;if (n < m) {temp = n;n = m;m = temp;}while (r != 0) {r = n % m;n = m;m = r;}System.out.print(a / n + " " + n);}}

*求最小公倍数算法：
最小公倍数：数论中的一种概念，两个整数公有的倍数成为他们的公倍数，其中一个最小的公倍数是他们的最小公倍数，同样地，若干个整数公有的倍数中最小的正整数称为它们的最小公倍数

最小公倍数=两整数的乘积÷最大公约数

证明的话，我可能写法不会太严谨，还是举个栗子吧：

求最小公倍数的常规方法：
首先把两个数的质因数写出来，最小公倍数等于它们所有的质因数的乘积（如果有质因数相同，则除去相同的质因数一次）。
比如求45和30的最小公倍数。
45=335
30=235

最小公倍数等于2335=90，用最大公约数15（35）乘以各自的其他部分的质因数（2和3），既保障数字是最小的，也保障是他们共同的倍数
所以最小公倍数也可以表示为：335235÷35 = 90

求最大公约数算法：
最小公约数：两个整数公有的约数成为他们的公约数，其中一个最大的公约数是他们的最大公约数

辗转相除法
1、用除法实现辗转相除法：

有两整数a和b：

① a%b得余数c

② 若c=0，则b即为两数的最大公约数

③ 若c≠0，则a=b，b=c，再回去执行①

例如求27和15的最大公约数过程为：

27÷15 余1215÷12余312÷3余0因此，3即为最大公约数*