C语言程序:求两个数的最大公约数

#include

<stdioh>

#include

<stdlibh>

//使用欧氏演算法求最大公约数

int

gcd(int

a,

int

b)

{

if

(a

<

b)

{

int

t

=

a;

a

=

b;

b

=

t;

}

if

(a

%

b

==

0)

{

return

b;

}

else

{

return

gcd(b,

a

%

b);

}

}

int

main()

{

printf("请输入两个数：\n");

int

a,

b;

scanf("%d",

&a);

scanf("%d",

&b);

printf("最大公约数为：%d",

gcd(a,

b));

return

0;

}

最大公约数算法：

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

不用辗转相除，只需要根据数学定义，找出最大的可以同时整除两个数值，即为最大公约数。

代码如下：

int gcd(int a,int b)//求a,b的最大公约数，并返回。

{

    int r = a>bb:a;

    while(r)

    {

        if(a%r==0 && b%r==0)break;//最大的可以同时整除二者的数，即为最大公约数。

        r--;

    }

    

    return r;

}

思路：求两个数的最大公约数使用辗转相除法。

辗转相除法，

又名欧几里德算法（Euclidean

algorithm）乃求两个正整数之最大公因子的算法。原理：两个整数的最大公约数等于其中较小的数和两数的差的最大公约数。

参考代码：

#include <stdioh>

int main()

{

int x,y,z;

scanf("%d%d",&x,&y);

while(x!=0)

{

z=x%y;

x=y;

y=z;

}

printf("%d\n",z);

return 0;

}

/

运行结果：

6 27

3

/

解题步骤：

1、求最大公约数

对两个正整数a,b如果能在区间[a,0]或[b,0]内能找到一个整数temp能同时被a和b所整除，则temp即为最大公约数。

2、求最小公倍数

对两个正整数a,b,如果若干个a之和或b之和能被b所整除或能被a所整除，则该和数即为所求的最小公倍数。

//穷举法求两数的最大公约数

int divisor(int a,int b)

{

int temp;//定义义整型变量

temp=(a&gt;b)b:a;//采种条件运算表达式求出两个数中的最小值

while(temp&gt;0){

if(a%temp==0&&b%temp==0)//只要找到一个数能同时被a,b所整除，则中止循环

break;

temp--;//如不满足if条件则变量自减，直到能被a,b所整除

}

return temp;//返回满足条件的数到主调函数处

}

//穷举法求两数的最小公倍数

int multiple(int a,int b)

{

int p,q,temp;

p=(a&gt;b)a:b;//求两个数中的最大值

q=(a&gt;b)b:a;//求两个数中的最小值

temp=p;//最大值赋给p为变量自增作准备

while(1){//利用循环语句来求满足条件的数值

if(p%q==0)

break;//只要找到变量的和数能被a或b所整除，则中止循环

p+=temp;//如果条件不满足则变量自身相加

}

return p;

}

扩展资料：

用穷举法解题时，就是按照某种方式列举问题答案的过程。针对问题的数据类型而言，常用的列举方法一有如下三种：

（1）顺序列举是指答案范围内的各种情况很容易与自然数对应甚至就是自然数，可以按自然数的变化顺序去列举。

（2）排列列举有时答案的数据形式是一组数的排列，列举出所有答案所在范围内的排列，为排列列举。

（3）组合列举当答案的数据形式为一些元素的组合时，往往需要用组合列举。组合是无序的。

例子如下：在公元五世纪我国数学家张丘建在其《算经》一书中提出了“百鸡问题”：

“鸡翁一值钱5，鸡母一值钱3，鸡雏三值钱1。百钱买百鸡，问鸡翁、母、雏各几何？”这个数学问题的数学方程可列出如下：

Cock+Hen+Chick=100

Cock5+Hen3+Chick/3=100

显然这是个不定方程，适用于穷举法求解。依次取Cock值域中的一个值，然后求其他两个数，满足条件就是解。

该问题的C语言程序算法如下：

int Cock,Hen,Chick;/定义公鸡，母鸡，鸡雏三个变量/

Cock=0;

while(Cock&lt;=19)/公鸡最多不可能大于19/

{Hen=0;

whlie(Hen&lt;=33)/母鸡最多不可能大于33/

{Chick=100-Cock-Hen;

if(Cock15+Hen9+Chick==300)/为了方便，将数量放大三倍比较/

printf("\n公鸡=%d\n母鸡=%d\n雏鸡=%d",Cock,Hen,Chick);

Hen=Hen+1;

}

Cock=Cock+1;

}

参考资料：

百度百科——穷举法

#include<stdioh>

int main()

{

int m, n, temp, i;

printf("Input m & n:");

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

if(m<n)  /比较大小，使得m中存储大数，n中存储小数/

{ /交换m和n的值/

temp=m;

m=n;

n=temp;

}

for(i=n; i>0; i--)  /按照从大到小的顺序寻找满足条件的自然数/

if(m%i==0 && n%i==0)

{/输出满足条件的自然数并结束循环/

printf("The GCD of %d and %d is: %d\n", m, n, i);

break;

}

return 0;

}

代码如下：

#include

int main()

{

int i,a,b,t;

scanf(%d%d,&a,&b);//输入数a,b

if(a>b)//比较a,b大小，如果a>b则交换，结果为a= 2; i--)//以较小的a为基数，每内次i减小1循环求最大公容约数

{

if (a % i == 0 && b % i == 0)//如果两数均能整除某数则该数为最大公约数

{

printf(最大公约数是：%dn,i);

break;//已得到最大公约数后跳出循环

}

}

if(i==1)//若循环到最后仍无最大公约数则i=1

printf(两数只能同时被1整除！n);

return 0;

}

最大公约数c语言编程的常用思路是：按照从大（两个整数中较小的数）到小（到最小的整数1）的顺序求出第一个能同时整除两个整数的自然数，即为所求。

两个数的最大公约数有可能是其中的小数，所以在按从大到小顺序找寻最大公约数时，循环变量i的初值从小数n开始依次递减，去寻找第一个能同时整除两整数的自然数，并将其输出。

需要注意的是，虽然判定条件是i>0，但在找到第一个满足条件的i值后，循环没必要继续下去，如，25和15，最大公约数是5，对于后面的4、3、2、1没必要再去执行，但此时判定条件仍然成立，要结束循环只能借助break语句。

具体代码实现：

#include<stdioh>

int main()

{

int m,n,temp,i;

printf("Input m&n:");

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

if(m<n)/比较大小，使得m中存储大数，n中存储小数/

{/交换m和n的值/

temp=m;

m=n;

n=temp;

}

for(i=n;i>0;i--)/按照从大到小的顺序寻找满足条件的自然数/

if(m%i==0&&n%i==0)

{/输出满足条件的自然数并结束循环/

printf("The GCD of%d and%d is:%d\n",m,n,i);

break;

}

return 0;

}

以上就是关于C语言程序:求两个数的最大公约数全部的内容，包括:C语言程序:求两个数的最大公约数、C语言程序设计如何求最大公约数、用c语言编写求最大公约数的程序 ，不需要辗转相除法，最简单的FOR循环或者Whlie就行等相关内容解答，如果想了解更多相关内容，可以关注我们，你们的支持是我们更新的动力！