最大公约数最小公倍数

痛定思痛。 2021-09-20 23:58 412阅读 0赞

最大公约数是两个及以上的数，能被所有的数整除的最大因子，就是这些数的最大公约数。

### 举个栗子： ###

8的因子1,2,4,8

12的因子1,2,4,6,12

很明显他们的最大约数4。约数即能以上的数约分的数8/4=0,12/4=0。

多个数求最大公约数方法相同。

### 最大公约数的特点： ###

*  最大为所给数中的最小的数
 *  最小为1

最小公倍数能被所给的所有数整除，即所给的数除以最小公倍数均为0。

### 举个栗子： ###

6和9的最小公倍数18。18/6=0,18/9=0。

### 最小公倍数的特点： ###

*  任意一个最小公倍数不会小于其中最大的数
 *  最小公倍数最大他们的乘积

最大公约数与最小公倍数的关系（设m、n两数的最大公约数为k），则最小公倍数=m\*n/k

以下展示辗转相除求最大公约数。

public class 递归辗转相除 {
    	/*
    	 用辗转相除法求几个数的最大公约数，可以先求出其中任意两个数的最大公约数，
    	 再求这个最大公约数与第三个数的最大公约数，依次求下去，直到最后一个数为0为止。
    	 最后所得的那个最大公约数，就是所有数的最大公约数。
    	最大公约数最小为1;
    	 */
    	public static void main(String[] args) {
    		//假设m>n,则辗转相除f(m,n) = f(n,m%n);
    		//辗转相除求最大公约数   ----> 最小公倍数为m*n/最大公约数
    		System.out.println(gcd(6,9)); // 4与2的最大公约数
    
    		
    		int m=35,n=5;
    		int tem = m % n;
    		while(tem != 0) {
    			n=m;
    			m = tem;
    			tem = n % m;
    		}
    		System.out.println(n);
    	}
    	
    	
    	/**
    	 * 递归求最大公约数
    	 * 欧几里德法:gcd(a,b) = gcd(b,a mod b)
    	 * @param m 第一个数 
    	 * @param n 第二个数
    	 */
    	static int gcd(int m, int n) {
    		if(m%n == 0)return n;
    		return gcd(n,m%n);
    	}
    }