求最大公约数算法

#include<stdio.h>
#include<stdlib.h>
int max_approximate(int num1, int num2)
{
	if (num1 > num2)
	{
		int tmp = 0;
		tmp = num1;
		num1 = num2;
		num2 = tmp;
	}
	int min = num1;
	while (min)
	{
		if ((num2%min == 0)&&(num1%min==0))
		{
			return min;
		}
		min--;
	}
	return 1;
}
int main()
{
	int num1 = 0;
	int num2 = 0;
	int ret = 0;
	scanf("%d%d", &num1,&num2);
	ret=max_approximate(num1, num2);
	printf("%d\n", ret);
	system("pause");
	return 0;
}

//辗转相除

int max_approximate(int num1, int num2)

{

    if (num1 > num2)

   {

     int tmp = 0;tmp = num1;

     num1 = num2;num2 = tmp;

   }

int r = num2%num1;

while (r != 0)

{

num2 = num1;

num1 = r;r = num2%num1;

}

return num1;

}

int main()

{

int num1 = 0;

int num2 = 0;

int ret = 0;

scanf("%d%d", &num1, &num2);

ret = max_approximate(num1, num2);

printf("%d\n", ret);system("pause");

return 0;

}

//更相减损法：

int max_approximate(int num1, int num2)

{

if (num1 > num2)

{

int tmp = 0;

tmp = num1;

num1 = num2;

num2 = tmp;

}

int r = num2-num1;

while (r != num1)

{if (num1>r)

{

num2 = num1;

num1 = r;

}

else

{

num2 = r;

}

r = num2-num1;

}

return num1;

}

int main()

{

int num1 = 0;

int num2 = 0;

int ret = 0;

scanf("%d%d", &num1, &num2);

ret = max_approximate(num1, num2);

printf("%d\n", ret);

system("pause");

return 0;

}

1.辗转相除法

算法：就是用大数除小数,如果余数不是零,就把余数和较小的数构成一组新数,继续上面的除法,知道大数被小数约尽,此时比较小的数就是最大公约数

2. 更相减损法：

更相减损术，是出自《九章算术》的一种求最大公约数的算法，它原本是为约分而设计的，但它适用于任何需要求最大公约数的场合。

       《九章算术》是中国古代的数学专著，其中的“更相减损术”可以用来求两个数的最大公约数，即“可半者半之，不可半者，副置分母、子之数，以少减多，更相减损，求其等也。以等数约之。”

翻译成现代语言如下：

第一步：任意给定两个正整数；判断它们是否都是偶数。若是，则用2约简；若不是则执行第二步。

第二步：以较大的数减较小的数，接着把所得的差与较小的数比较，并以大数减小数。继续这个操作，直到所得的减数和差相等为止。

则第一步中约掉的若干个2与第二步中等数的乘积就是所求的最大公约数。

其中所说的“等数”，就是最大公约数。求“等数”的办法是“更相减损”法。所以更相减损法也叫等值算法。

   3. 辗转相除法与更相减损术的区别

（1）都是求最大公因数的方法，计算上辗转相除法以除法为主，更相减损术以减法为主，计算次数上辗转相除法计算次数相对较少，特别当两个数字大小区别较大时计算次数的区别较明显。

（2）从结果体现形式来看，辗转相除法体现结果是以相除余数为0则得到，而更相减损术则以减数与差相等而得到

4.个数的最大公约数与最小公倍数的乘积就是这两个数的乘积,可以转化求最小公倍数。