c语言求最大公约数，最小公倍数

写c语言题目时，我们经常会遇到求最大公约数和最小公倍数的问题。为了方便学习，我整理了一些用c语言求最大公约数的方法。

#最大公约数？

最大公约数，指两个或多个整数共有约数中最大的一个。

举例说，

能够整除一个整数的整数称为其的约数（如5是10约数）；

如果一个数既是数m的约数c语言求最大公约数，又是数n的约数，称为m,n的公约数。m,n的公约数中最大的一个（可以包括m,n自身）称为m,n的最大公约数。

#更相减损术方法

利用更相减损术求两个整数的最大公约数，即每次将较大的数变成大数减去小数的值，当满足循环条件(两数相等）输出结果即可。

举例说，若m=4，n=6c语言求最大公约数，则m!=n且mn=2，此时m>n，执行m=m-n->m=2，m=n，输出最大公约数m=2。

#include
int main(){
    int m,n;
    scanf("%d %d",&m,&n);
    while(m!=n){     //相等即得最大公约数

     if(mn){
        n=n-m;
    }else if(m>n){
        m=m-n;
    }   
}
    printf("%d",m);
}

#辗转相除法

当两个数都较大时，我们一般采用辗转相除法比较方便。

即以小数除大数，如果能整除，那么小数就是所求的最大公约数；否则就用余数来除刚才的除数；若不能整除，将得到新的余数去除刚才的余数。以此类推，直到一个除法能够整除，这时作为除数的数就是所求的最大公约数。

#include 
int main()

{
	int m,n,t,a,b;
	scanf("%d,%d",&m,&n);
	if(mn){
      t=m;m=n;n=t;
	}
	a=m;
	b=n;
	while(b!=0){ /*①a%b得余数c ②若c=0,则b即为两数的最大公约数
③若c≠0，则a=b，b=c，再回去执行①*/ 
	   t=a%b;
	   a=b;
	   b=t;	
	}

	printf("%d",a);    
	return 0;
} 

#穷举法

#include
int main(){
	int m,n,i,t;
	scanf("%d %d",&m,&n);
	if(mn){
		t=m;m=n;n=t;
	}
	for (i = m; i > 0; i--){
		if ((m%i == 0) && (n%i == 0)){

			break;
		}
	}
	printf("%d",i);
} 

#最小公倍数？

如果一个数既是a又是b的倍数且这个数在a，b的所有公倍数里为最小，那这个数就是最小公倍数。

解题重点：最小公倍数=两整数的乘积÷最大公约数

#include 
int main()
{
	int m,n,t,gys,gbs,a,b;
	gys=0;gbs=0;

	scanf("%d,%d",&m,&n);
	if(mn)
	{t=m;m=n;n=t;}
	a=m;
	b=n;
	while(b!=0)    
	{
	   t=a%b;
	   a=b;
	   b=t;	
	}
	printf("gys=%d,gbs=%d",a,m*n/a);   
	return 0;
} 

标签： #最大公约数