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

一时失言乱红尘 2022-12-13 04:14 101阅读 0赞

## 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 stub
    		Scanner 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=3*3*5  
30=2*3*5

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

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

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

有两整数a和b：

① a%b得余数c

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

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

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