c中最大公约数的算法

‘壹’ 如何用C语言求两个数的最大公约数的三种算法

1、相减法

#include<stdio.h>

int main()

{

int a,b;

int c=0;//计数器

while(1)//循环判断的作用

{

printf("输入两个数字求最大公约数:");

scanf("%d%d",&a,&b);

while(a!=b)

{

if(a>b)

a=a-b;

else

b=b-a;

c++;

}

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

printf("%d ",c);

}

return 0;

}

运行效果：

2、辗转相除法：

#include<stdio.h>

int a,b,temp;

int Division(){

printf("请输入两个数(a,b)： ");

scanf("%d,%d",&a,&b);

if(a<b){

temp=a;

a=b;

b=temp;

}

while(a%b!=0){

temp=a%b;

a=b;

b=temp;

}

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

return 0;

}

3、穷举法

#include<stdio.h>

int main()

{

int a,b,c;

int d=0;//计数器

while(1)

{

printf("输入两个数字求最大公约数:");

scanf("%d%d",&a,&b);

c=(a>b)?b:a;//三目运算符

while(a%c!=0||b%c!=0)

{

c--;

d++;

}

printf("最大公约数是:%d ",c);

printf("%d ",d);

}

return 0;

}

‘贰’ c语言求最大公约数

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

‘叁’ c语言如何求最小公倍数和最大公约数

解题步骤：

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>b)?b:a;//采种条件运算表达式求出两个数中的最小值

while(temp>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>b)?a:b;//求两个数中的最大值

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

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

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

if(p%q==0)

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

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

}

return p;

}

(3)c中最大公约数的算法扩展阅读：

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

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

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

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

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

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

Cock+Hen+Chick=100

Cock*5+Hen*3+Chick/3=100

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

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

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

Cock=0;

while(Cock<=19)/*公鸡最多不可能大于19*/

{Hen=0;

whlie(Hen<=33)/*母鸡最多不可能大于33*/

{Chick=100-Cock-Hen;

if(Cock*15+Hen*9+Chick==300)/*为了方便，将数量放大三倍比较*/

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

Hen=Hen+1;

}

Cock=Cock+1;

}

‘肆’ 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--，再回去执行②

‘伍’ 求最大公约数c语言

c语言求最大公约数有辗转相除法、更相减损术、穷举法三种。

最大公约数：

最大公因数，也称最大公约数、最大公因子，指两个或多个整数共有约数中最大的一个。a，b的最大公约数记为（a，b），同样的，a，b，c的最大公约数记为（a，b，c），多个整数的最大公约数也有同样的记号。

早在公元前300年左右，欧几里得就在他的着作《几何原本》中给出了高缓好卜效的解法——辗转相除法。辗转相除法使用到的原理很聪明也很简单，假设用f（x，y）表示x，y的最大公约数，取k=x/y，b=x%y，则x=ky+b，如果一个数能够同扰穗时整除x和y，则必能同时整除b和y。

而能够同时整除b和y的数也必能同时整除x和y，即x和y的公约数与b和y的公约数是相同的，其最大公约数也是相同的，则有f（x，y）=f（y，x%y）（y>0），如此便可把原问题转化为求两个更小数的最大公约数，直到其中一个数为0，剩下的另外一个数就是两者最大的公约数。