最大公约数与最小公倍数

最大公约数

1、欧几里德算法 GCD(A,B) = GCD(B, A%B);

证明：a可以表示成a = kb + r，则r = a mod b
假设d是a,b的一个公约数，则有
d|a, d|b，而r = a - kb，因此d|r
因此d是(b,a mod b)的公约数

假设d 是(b,a mod b)的公约数，则
d | b , d |r ，但是a = kb +r
因此d也是(a,b)的公约数

因此(a,b)和(b,a mod b)的公约数是一样的，其最大公约数也必然相等，得证

   递归实现代码：

	/**
	 * 递归实现最小公约数 
	 * ---- 欧几里德算法
	 * @param a
	 * @param b
	 * @return
	 */
	public static int GCDOuJiLiDe(int a, int b) {
		if (b == 0) return a;
		return GCDOuJiLiDe(b, a % b);
	}

 

 

     

 非递归实现代码：

 

 

/**
	 * 非递归实现最小公约数
	 * ---- 欧几里德算法
	 * @param a
	 * @param b
	 * @return
	 */
	public static int GCDUsingWhile(int a, int b) {
		while (b != 0) {
			int r = b;
			b = a % b;
			a = r;
		}
		return a;
	}

 

 2、Stein算法：

如果A=0，B是最大公约数，算法结束
如果B=0，A是最大公约数，算法结束
设置A1 = A、B1=B和C1 = 1
如果An和Bn都是偶数，则An+1 =An /2，Bn+1 =Bn /2，Cn+1 =Cn *2(注意，乘2只要把整数左移一位即可，除2只要把整数右移一位即可)
如果An是偶数，Bn不是偶数，则An+1 =An /2，Bn+1 =Bn ，Cn+1 =Cn (很显然啦，2不是奇数的约数)
如果Bn是偶数，An不是偶数，则Bn+1 =Bn /2，An+1 =An ，Cn+1 =Cn (很显然啦，2不是奇数的约数)
如果An和Bn都不是偶数，则An+1 =|An -Bn|，Bn+1 =min(An,Bn)，Cn+1 =Cn
n++，转4

代码实现：

 

	/**
	 * 实现最小公约数
	 * Stein算法
	 * @param a
	 * @param b
	 * @return
	 */
	public static int GCDUsingStein(int a, int b) {
		if (a == 0) return b;
		if (b == 0) return a;
		if (a % 2 == 0 && b % 2 == 0) return GCDUsingStein(a >> 1, b >> 1) << 1;
		else if (a % 2 == 0 && b % 2 != 0) return GCDUsingStein(a >> 1, b);
		else if (a % 2 != 0 && b % 2 == 0) return GCDUsingStein(a, b >> 1);
		else return GCDUsingStein(Math.abs(a - b), Math.min(a, b));
	}

 

最小公倍数 = 2数乘积 / 2数最大公约数