编程求最大公约数

① c语言编程_穷举法求两个数的最大公约数

求最大公约数算法：
(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) );
}

② c语言编程，求两个数的最大公约数和最小公倍数

这样写：
#include
void
main()
{
int
m,n,i,r,temp;
printf("请输入第一个数的值:
");
scanf("%d",&m);
printf("请输入第二个数的值:
");
scanf("%d",&n);
if(n>m)
{
temp=m;
m=n;
n=temp;
}
i=n;
while(i%m!=0)
{
i=i+n;
}
printf("最小公倍数是:%d
\n",i);
r=m%n;
while(r!=0)
{
m=n;
n=r;
r=m%n;
}
printf("最大公约数是:%d
\n",n);
}
图：

③ c语言编程：输入两个正整数，求最大公约数和最小公倍数

#include

voidmain(){

inta,b,n1,n2,t;

while(true)

{

printf("任意输入两个正整数: ");

scanf("%d%d",&n1,&n2);

if(n1

{

t=n1;

n1=n2;

n2=t;

}

a=n1;

b=n2;

while(b!=0){/*利用辗除法，直到b为0为止*/

t=a%b;

a=b;

b=t;

}

printf("最大公约数为:%d ",a);

printf("最小公倍数为:%d ",n1*n2/a);

}}

(3)编程求最大公约数扩展阅读

C语言求最大公约数辗转相除法

#include<stdio.h>

intgcd(intm,intn);//将辗转相除的过程封装为函数，使主函数结构清晰。

intmain(void)

{

inta,b;

while(~scanf("%d%d",&a,&b)){//多组数据输入时的方式之一与while(scanf("%d%d",&a,&b)!=EOF)用途相同

printf("%d ",gcd(a,b));

return0;

}

intgcd(intm,intn)

{

returnn?gcd(n,m%n):m;//此函数将辗转相除的过程以递归的形式呈现，简化程序属于常规套路。

}

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

具体操作步骤如下：

一、新建一个C语言源程序，使用Visual C++6.0的软件。

⑤ C语言编程：输入两个正整数m和n，求它们的最大公约数。

#include <stdio.h>

int gcd(int a,int b)

{

if(a%b)

return gcd(b,a%b);

return b;

}

int main()

{

int m,n;

scanf("%d%d",&m,&n);

printf("%d ",gcd(m,n));

return 0;

}

⑥ c语言编程求输入两个数的最大公约数和最小公倍数，怎么做

输入两个正整数m和n,求其最大公约数和最小公倍数.用辗转相除法求最大公约数 算法描述:m对n求余为a,若a不等于0 则 m 0)
{
m_cup = m;

#include<stdio.h>

voidmain()

{

intm,n,m1,n1,t;

printf("请输入两个数(用空格隔开)：");

scanf("%d%d",&m,&n);

if(n>m)

{

t=m;

m=n;

n=t;

}

m1=m;

n1=n;

while(n!=0)

{

t=m%n;

m=n;

n=t;

}

printf("%d和%d的最大公约数是:%d ",m1,n1,m);

printf("最小公倍数是:%d ",m1*n1/m);

}

⑦ c语言编程：输入两个正整数m和n，求其最大公约数和最小公倍数。

输入两个正整数m和n，求其最大公约数和最小公倍数。

解：程序：

#include <stdio.h>

int main()

{

int num1, num2, t,p;

printf("请输入两个正整数：");

scanf("%d,%d", &num1, &num2);//7,8

p = num1*num2;

while (t = num1%num2)//7 1 0，循环结束

{

num1 = num2; //8 7

num2 = t; //7,循环继续 1

}

p = p / num2;

printf("它们的最大公约数：%d ", num2);

printf("它们的最小公倍数：%d ", p);

return 0;

}

结果：

请输入两个正整数：3,6

它们的最大公约数：3

它们的最小公倍数：6

(7)编程求最大公约数扩展阅读：

C语言编写注意事项：

1、每个程序中一定包含main()函数，尽管C语言中对函数命名没有限制。

2、printf函数永远不会自动换行，只能用 来实现，回车键进行的换行在编译中会出现错误信息。

3、在vs2008中编译，测试需要加 system("pause")；来暂停dos自动退出导致的printf无法显示。

4、每行只书写一条语句，在运算符两边加上一个空格，便于阅读。

⑧ c语言求最大公约数

1、新建一个C语言源程序，这里使用Visual C++6.0的软件：

⑨ c语言求两个数的最大公约数是多少

c语言求两个数的最大公约数的步骤如下：

1、首先，新建一个C语言源程序，在这里使用的是Visual C++6.0的软件。

以上就是c语言求两个数的最大公约数的步骤了。