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

发布网友 发布时间：2022-04-22 04:19

我来回答

共5个回答

热心网友 时间：2024-07-22 02:33

最大公约数算法：

(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--，再回去执行②

热心网友 时间：2024-07-22 02:34

#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;
}

热心网友 时间：2024-07-22 02:33

源程序如下：
#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;
}
忙了半天，请加分采纳，谢谢了

热心网友 时间：2024-07-22 02:39

求最大公约数算法：

(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_(int a,int b)
{
int c;
c=a%b;
while( c!=0 )
{
a=b;
b=c;
c=a%b;
}
return b;
}
int xj_(int a,int b)
{
while( a!=b )
{
if ( a>b )
a-=b;
else
b-=a;
}
return b;
}
int qj_(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_(a,b) );
printf("相减法求最大公约数=%d\n", xc_(a,b) );
printf("穷举法求最大公约数=%d\n", xc_(a,b) );
}

运行效果图：

热心网友 时间：2024-07-22 02:36

//常规方法
#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));
}