一、辗转相除法（欧几里得算法）1、定义：所谓辗转相除法，就是对于给定的两个数，用较大的数除以较小的数。若余数不为零，则将余数和较小的数构成新的一对数，继续上面的除法，直到大数被小数除尽，则这时较小的数就是原来两个数的最大公约数。
最大公约数与最小公倍数的求解是很多初学C的人所面临的一个问题，接下来为大家提供方法。
问题：
请从键盘上输入两个数值 x，y，请用C语言求出这两个数值的最大公约数与最小公倍数。
int divisor (int a,int b) /*自定义函数求两数的最大公约数*/ { int temp; /*定义整型变量*/ if(a
最大公因数；也称最大公约数、最大公因子，指两个或多个整数共有约数中最大的一个。
#include void main(){int m,n,k;scanf("%d%d",&m,&n);while(n) {k=m%n;m=n;n=k;}printf("%d",m);}
最小公倍数：两个或多个整数公有的倍数叫做它们的公倍数。
举个例子你就懂了： 用辗转相除法或更相减损术求324,243,135的最大公约数 先求两个较大数324与243的最大公约数 324/243=181 243/81=3 知324与243的最大公约数是81 或 324-243=81 243-81=162 162-81=81 知324与243的最大公约数是81 再求81与较
辗转相除法
又名欧几里德算法（Euclidean algorithm），它是已知最古老的算法， 其可追溯至公元前300年前。辗转：望文生义，就是翻来覆去。相除就很好理解了，就是进行除法运算。辗转相除法的核心就是不断的让两个数做除法运算。其原理基于两个整数的最大公约数等于其中较小的数和两数的相除余数的最大公约数。假设两数为 x，y。先令 z = x % y ；之后 y 赋给 x 即令x = y ；再将 z 赋给 y 即令y = z；辗转相减，其终止条件为：y 等于0时。
辗转相除法，是求两个正整数之最大公因子的算法。 辗转相除法的算法过程如下：设两数为a、b(a>b)，求a和b最大公约数(a，b)的步骤如下：用a除以b，得 a÷b=q，余数r1(0≤r1)。若r1=0，则(a，b)=b；若r1不等于0，则再用b除以r1，得b÷r1=q，余数r2 (0
代码如下：
辗转相减法
即尼考曼彻斯法，其特色是做一系列减法，从而求得最大公约数。辗转相减法即通过对两数的不断减法运算。假设两数为 x, y。当 x > y 时，令 x = x - y；反之，则令 y = y - x；之后一直辗转相减，直至 x = y 时，终止。
辗转相除法求两个数a和b的最大公约程序如下： 程式解析如下： 设两数为a、b(b1），则m=kn+xd=kyd+xd=(ky+x)d，则a=mc=(ky+x)dc，b=nc=ycd，故a与b最大公约数成为cd，而非c】 从而可知(b,r)=c，继而(a,b)=(b,r）。 证毕。 扩展资料VB语
代码如下：
穷举法
穷举法的基本思想是根据题目的部分条件确定答案的大致范围，并在此范围内对所有可能的情况逐一验证，直到全部情况验证完毕。穷举法又称枚举法，通过对数值范围内的所有数字进行检验，得出其结果。
可用递归来求。 推荐以下代码： #includeint (int a,int b) //求最大公约数函数{if (a%b==0) return b;else return (b,a%b); //辗转相除法}void main(){int a,b;scanf("%d%d",&a,&b);printf("%dn",(a,b));}
代码如下：
扩展阅读，以下内容您可能还感兴趣。
辗转相除法为什么能求最大公约数
可以维基、百度百科，
简单来说，被除数被分成了两坨，一坨可以被整除，一坨是余数，现在都可以被整除的玩意必然也可以被最后的最大公约数整除，所以只用找余数与除数的最大公因数，然后同理，余数与除数又分别成了被除数和除数，直至最后整除
编程一个C语言程序,输入两个数,采用辗转相除法来计算最大公约数
可以参考下面的代码：
#include <stdio.h>
int main()
{
int m, n, r;
scanf ("%d%d", &m, &n);
if (m>n){r=m, m=n, n=r;}
r=n%m;
while (r!=0){
n = m;
m = r;
r = n%m;
}
printf ("%dn", m);
return 0;
}
扩展资料：
函数 scanf() 是从标准输入流stdin(标准输入设备，一般指向键盘)中读内容的通用子程序，可以说明的格式读入多个字符，并保存在对应地址的变量中。
函数的第一个参数是格式字符串，它指定了输入的格式，并按照格式说明符解析输入对应位置的信息并存储于可变参数列表中对应的指针所指位置。每一个指针要求非空，并且与字符串中的格式符一一顺次对应。
参考资料来源：百度百科-scanf （计算机语言函数）
参考资料来源：百度百科-while （循环语句及英文单词）
c语言用辗转相除法求最大公约数
你没发图我不知道你的程序有什么问题，给出我的代码：#include<stdio.h>
int *(int a,int b){
return a%b?*(b,a%b):b;
}
int main(){
printf("%d",*(4,6));
return 0;
}
运行结果：更多追问追答追问不好意思，忘记发图了追答看不清。。追问哦哦，我已经知道自己错哪了，但是不知道为什么错#include
int main()
{
int a,b,rem;
int *;
printf("Enter 2 integers:");
scanf("%d,%d",&a,&b);
....
}
运行时我输入a和b中间用的是空格，而不是逗号，所以错了，但是为什么是个负数呢。。。我输入125 45
然后结果是－5应该是5才对啊
为啥辗转相除法可以求最大公约数
辗转相除法求最大公约数原理：
设两数为a、b(a>b)，用*(a,b)表示a，b的最大公约数，r=a (mod b) 为a除以b的余数，k为a除以b的商，即a÷b=k.......r。辗转相除法即是要证明*(a,b)=*(b,r)。
第一步：令c=*(a,b)，则设a=mc，b=nc
第二步：根据前提可知r =a-kb=mc-knc=(m-kn)c
第三步：根据第二步结果可知c也是r的因数
第四步：可以断定m-kn与n互质(假设m-kn=xd，n=yd (d>1)，则m=kn+xd=kyd+xd=(ky+x)d，则a=mc=(ky+x)cd，b=nc=ycd，则a与b的一个公约数cd>c，故c非a与b的最大公约数，与前面结论矛盾)，因此c也是b与r的最大公约数。
从而可知*(b,r)=c，继而*(a,b)=*(b,r)。
证毕。
以上步骤的操作是建立在刚开始时r≠0的基础之上的。即m与n亦互质。
给我讲一下用短除法和辗转相除法求最大公约数
辗转相除法：
要求a、b两个整数的最大公约数，a＞b，那么我们先用a除以b，得到商 q1，余数r1：a÷b＝q1…r1我们当然也可以把上面这个式子改写成乘法式：
a＝b * q1＋r1
如果r1＝0，那么b就是a、b的最大公约数3。要是r1≠0，就继续除，用b除以r1，我们也可以有和上面一样的式子：
b＝r1q2＋r2
如果余数r2＝0，那么r1就是所求的最大公约数3。因为如果b＝r1q2＋r2变成了b＝r1q2，那么b1r1的公约数就一定是a1b的公约数。这是因为一个数能同时除尽b和r1，那么由a＝b * q1＋r1，就一定能整除a，从而也是a1b的公约数。
反过来，如果一个数d，能同时整除a1b，那么由1）式，也一定能整除r1，从而也有d是b1r1的公约数。
这样，a和b的公约数与b和r1的公约数完全一样，那么这两对的最大公约数也一定相同。那b1r1的最大公约数，在r1＝0时，不就是r1吗？所以a和b的最大公约数也是r1了。
如果r2不是0，用r1除以r2，……直到余数为零为止。
短除法
如例子：
2|_18__30__
3|_9__15__
3 5
其实短除法就是放到一起慢慢约分，对于简单的还有效，而大一点的数还是辗转相除法比较有效，而且辗转相除法的逻辑性也为计算机编程提供了条件
