求俩个数的最大公约数、最小公倍数

求最大公约数的三种方法，最小公倍数在最大公约数的基础上求得。

1.辗转相除法（又名欧几里得算法）

最小公倍数为 俩个数的乘积除以它们的最大公约数

求两个数的最大公约数常用辗转相除法
被除数 除 除数,若能整除 ,除数即为其最大公约数；
若不能整除,被除数和除数的最大公约数等于除数和余数的最大公约数,所以把原来的除数做被除数,余数做除数,再相除,
若能整除 ,除数即为其最大公约数；若不能整除,再把原来的除数做被除数,余数做除数,再相除,如此反复进行,知道除尽,而得出最大公约数.

代码和结果演示：

#define _CRT_SECURE_NO_WARNINGS 1	
#include<stdio.h>
#include<stdlib.h>
 int main()
{
	int a = 0, b = 0, c = 0, d = 0;
	int dou = 0;
	int num1 = 0, num2 = 0;
	printf("请输入要求最大公因数的俩个数值：\n");
	scanf("%d %d", &a, &b);
	
	    num1 = a;      //后面a,b赋值会改变a,b原来输入时的值，故在此附给num,使其保留原值；
		num2 = b; 
		
	if (b > a)
	{
		c = b;
		b = a;
		a = c;
	}
	d = a % b;
	while (d != 0)               //依次相除，直至d==0;
	{
		a = b;
		b = d;
		d = a % b;
	}
	printf("俩数的最大公因数是：%d\n", b);

	dou = (num1*num2) /b;
	printf("俩数的最小公倍数是：%d\n", dou);

	system("pause");
	return 0;
}

上面代码的改进

不需要进行比较，小数%大数 比 大数%小数多进行一次
例如：21%9=3，而9%21=9（不够商1，就商0，余数就等于被除数）
3%7=3 ， 7%10=7， 10%20=10

#define _CRT_SECURE_NO_WARNINGS 1	
#include<stdio.h>
#include<stdlib.h>
//求俩个数的最大公约数、最小公倍数：
int main()
{
	int m= 0;
	int n = 0;
	int r = 0;
	printf("请输入要求最大公因数的俩个数值：\n");
	scanf("%d %d", &m, &n);
	while( n % m )
	{
		r = n % m;
		n = m;
		m = r;
	}
	printf("俩数的最大公因数是：%d\n", m);

	system("pause");
    return 0;

}

2.更相减损术

以两数中较大的数减去较小的数，获得的差与原先较小的数构成新的一对数，在以大的数减去小的数，依次循环。用同样的方法操作，直至产生一对相等的数为止，该数即为最大公约数。

代码

#define _CRT_SECURE_NO_WARNINGS 1	
#include<stdio.h>
#include<stdlib.h>
//求俩个数的最大公约数、最小公倍数：

int main()
{
	int n, a, b, c;
	n = 1;
	printf("请输入两个整数 :");
	scanf("%d %d", &a, &b);
	if (a < b)
	{
		a = a ^ b;
		b = a ^ b;
		a = a ^ b;
	}
	while (n != 0)
	{
		a = a - b;
		if (a < b)
		{
			a = a ^ b;    //异或操作，交换俩个数值
			b = a ^ b;
			a = a ^ b;
		}
		if (a == b)
		{
			n = 0;
		}
	}
	printf("\n最大公约数是:%d\n", b);
	system("pause");
}