本文共 1059 字，大约阅读时间需要 3 分钟。

前言

写写最大公约数

正文

几个概念:

辗转相除法,欧几里得算法。

两个正整数a 和 b (a>b),它们的最大公约数等于a处于b的余数c和b直接的最大公约数。

public static int generateGreatestCommonDivisor(int a,int b){	var max=a>b?a: b;	var min = a > b ? b : a;	if (max % min == 0)	{		return min;	}	else	{		var yu = max % min;		return generateGreatestCommonDivisor(min, yu);	}}

更相减损数

两个正整数a和 b(a>b),它们的最大公约数等于a-b的差值c与b的最大公约数

public static int generateGreatestCommonDivisor(int a, int b){	if (a == b)	{		return a;	}	var max = a > b ? a : b;	var min = a > b ? b : a;   return  generateGreatestCommonDivisor(min,max-min);}

两者结合

public static int generateGreatestCommonDivisor(int a, int b){	if (a == b)	{		return a;	}	if (((a & 1) == 0 && (b & 1) == 0))	{		return generateGreatestCommonDivisor(a >> 1, b >> 1) << 1;	}	else if (((a & 1) == 0 && (b & 1) != 0))	{		return generateGreatestCommonDivisor(a >> 1, b);	}	else if (((a & 1) != 0 && (b & 1) == 0))	{		return generateGreatestCommonDivisor(a >> 1, b);	}	else	{		int big = a > b ? a : b;		var small = a > b ? b : a;		return generateGreatestCommonDivisor(big-small,small);	}}

总结

数学博大精深！