Question

C语言程序设计如何求最大公约数

Answer 1

最大公约数算法：

(1)辗转相除法

两整数a和b：

① a%b得余数c

② 若c=0，则b即为两数的最大公约数，结束

③ 若c≠0，则a=b，b=c，再回去执行①

(2)相减法

两整数a和b：

① 若a>b，则a=a-b

② 若a<b，则b=b-a

③ 若a=b，则a（或b）即为两数的最大公约数，结束

④ 若a≠b，则再回去执行①

(3)穷举法：

① i= a b中的小数

② 若a，b能同时被i整除，则i即为最大公约数，结束

③ i--，再回去执行②

Answer 2

求最大公约数算法：

(1)辗转相除法

两整数a和b：

① a%b得余数c

② 若c=0，则b即为两数的最大公约数，结束

③ 若c≠0，则a=b，b=c，再回去执行①

(2)相减法

两整数a和b：

① 若a>b，则a=a-b

② 若a<b，则b=b-a

③ 若a=b，则a（或b）即为两数的最大公约数，结束

④ 若a≠b，则再回去执行①

(3)穷举法：

① i= a b中的小数

② 若a，b能同时被i整除，则i即为最大公约数，结束

③ i--，再回去执行②

相关代码：

#include <stdio.h>
int xc_gcd(int a,int b)
{
	int c;
	c=a%b;
	while( c!=0 )
	{
		a=b;
		b=c;
		c=a%b;
	}
	return b;
}
int xj_gcd(int a,int b)
{
	while( a!=b )
	{
		if ( a>b )
			a-=b;
		else
			b-=a;
	}
	return b;
}
int qj_gcd(int a,int b)
{
	int i;
	i=(a>b)?a:b;
	while( a%i!=0 && b%i!=0 )
		i--;
	return i;
}
void main()
{
	//int a=36,b=27;
	//int a=27,b=36;
	int a=100,b=201;
	printf("a=%d b=%d\n", a, b );
	printf("辗转相除法求最大公约数=%d\n", xc_gcd(a,b) );
	printf("相减法求最大公约数=%d\n", xc_gcd(a,b) );
	printf("穷举法求最大公约数=%d\n", xc_gcd(a,b) );
}

运行效果图：

Answer 3

//常规方法
#include "stdio.h"
int main()
{
int d1,d2,r;
printf("输入两个正整数：");
scanf("%d %d",&d1,&d2);
do
{
r=d1%d2;
d1=d2;d2=r;
}while(d2!=0);
printf("最大公约数是：%d",d1);
}

//递归法
#include "stdio.h"
int fun(int d1,int d2)
{
if(d2!=0)
return fun(d2,d1%d2);
else
return d1;
}
int main()
{
int d1,d2;
printf("输入两个正整数：");
scanf("%d %d",&d1,&d2);
printf("最大公约数是：%d",fun(d1,d2));
}

Answer 4

源程序如下：
#include<stdio.h>
#include<math.h>
int fun_y(int,int);
int main()
{
int a,b,gy,gb;
printf("输入两个整数:\n");
scanf("%d%d",&a,&b);
gy=fun_y(a,b);
printf("最大公约数是：%d\n",gy);
return 0;
}
int fun_y(int x,int y)
{
int z,i;
if(x>y)
z=int(sqrt(y));
else
z=sqrt(x);
for(i=z;i>=1;i--)
{
if(x%i==0&&y%i==0)
break;
}
return i;
}
忙了半天，请加分采纳，谢谢了

Answer 5

#include<stdio.h>
int main()
{
int a,b,num1,num2,temp;
printf("please input num1 and num2: ");
scanf("%d%d",&num1,&num2);
if(num1 >= num2)
{
a = num1;
b = num2;
}
if(num1 < num2)
{
a = num2;
b = num1;
}
while(b > 0)
{
temp = a % b;
a = b;
b = temp;
}
printf("最大公约数是%d\n",a);
return 0;
}