求最大公约数

辗转相除法, 又名欧几里德算法(Euclidean algorithm),是求最大公约数的一种方法。它的具体做法是:用较小数除较大数,再用出现的余数(第一余数)去除除数,再用出现的余数(第二余数)去除第一余数,如此反复,直到最后余数是0为止。如果是求两个数的最大公约数,那么最后的除数就是这两个数的最大公约数。
目的:求两个整数的最大公约数
最大公约数:能同时被两个整数整除的最大公约数
 

#include<stdio.h>
int gcd(int a,int b);
int main(){
	int a,b;
	int t;//余数 
	int s;//商
	int temp;
	printf("请输入两个正整数:\n");
	scanf("%d %d",&a,&b);
	
	if(a<b)  //交换a,b值
	{
	temp=b;
	b=a;
	a=temp;
	}
	printf("被除数a=%d,除数b=%d,商s=%d,余数t=%d\n",a,b,a/b,a%b);
	while(b!=0){
		t=a%b;//必须a>b 
		a=b;//除数作被除数 
		b=t;//余数作除数 
		if(b==0)
			break;
		printf("a=%d,b=%d,t=%d\n",a,b,t); //b做除数,不能为0
		
	}
	printf("gcd=%d\n",a);
	return 0;
}


int gcd(int a,int b){
    if(b==0) 
		return a;
    else 
		return gcd(b,a%b);
} 

上一篇:求最小公因数算法


下一篇:P1888 三角函数