最大公约数怎么求算法
求最大公约数有多种方法，常见的有质因数分解法、短除法、辗转相除法、更相减损法。
1、质因数分解法
把每个数分别分解质因数，再把各数中的全部公有质因数提取出来连乘，所得的积就是这几个数的最大公约数。
例如：求24和60的最大公约数，先分解质因数，得24=2×2×2×3，60=2×2×3×5，24与60的全部公有的质因数是2、2、3，它们的积是2×2×3=12，所以，（24，60）＝12。
2、短除法
短除法求最大公约数，先用这几个数的公约数连续去除，一直除到所有的商互质为止，然后把所有的除数连乘起来，所得的积就是这几个数的最大公约数。
3、辗转相除法
辗转相除法也叫欧几里德算法。用辗转相除法求几个数的最大公约数，可以先求出其中任意两个数的最大公约数，再求这个最大公约数与第三个数的最大公约数，依次求下去，直到最后一个数为止。最后所得的那个最大公约数，就是所有这些数的最大公约数。
4、更相减损法
也叫更相减损术，是出自《九章算术》的一种求最大公约数的算法，它原本是为约分而设计的，但它适用于任何需要求最大公约数的场合。
《九章算术》是中国古代的数学专著，其中的“更相减损术”可以用来求两个数的最大公约数，即“可半者半之，不可半者，副置分母、子之数，以少减多，更相减损，求其等也。以等数约之。”
翻译成现代语言如下：
第一步：任意给定两个正整数；判断它们是否都是偶数。若是，则用2约简；若不是则执行第二步。
第二步：以较大的数减较小的数，接着把所得的差与较小的数比较，并以大数减小数。继续这个操作，直到所得的减数和差相等为止。
则第一步中约掉的若干个2与第二步中等数的乘积就是所求的最大公约数。
其中所说的“等数”，就是最大公约数。求“等数”的办法是“更相减损”法。所以更相减损法也叫等值算法。
扩展欧几里德算法
扩展欧几里得算法（又称扩充欧几里得算法）是用来解某一类特定的不定方程的一种方法，常用用来求解模线性方程及方程组。扩展的欧几里得算法可以用来计算模逆元，而模逆元在公钥密码学中占有举足轻重的地位。
基本算法：对于不完全为 0 的非负整数 a，b，gcd（a，b）表示 a，b 的最大公约数，必然存在整数对 x，y ，使得 gcd（a，b）=ax+by。
~
#于狄舍# 最大公约数如何求
(17744202034)： 这是古希腊的求法,并不是中国的,但道理一样的,就是大的数减小的,一直减到两个数相等,那么这个数就是最大公约数!
#于狄舍# 如何求最大公约数?
(17744202034)： 就是几个数共有的最大的因子,比如9,18,27 9=3*3,18=2*3*3,27=3*3*3,那么最大公约数=3*3=9
#于狄舍# 求两个数的最大公约数的方法叫啥了/ -
(17744202034)： 辗转相除法辗转相除法, 又名欧几里德算法(Euclidean algorithm)乃求两个正整数之最大公因子的算法.它是已知最古老的算法, 其可追溯至3000年前.简介 辗转相除法的演示动画在数学中,辗转相除法,又称欧几里得算法,是求最大公约...
#于狄舍# 求最大公约数的算法要小学的18和2722和6615,20和3024,42和72帮忙啊 - 作业帮
(17744202034)：[答案] main(){ intm=42,n=72; while(m!=n){ if(m>n){inttemp=m;m=n;n=temp;} n-=m; } printf(＂%d＂,m); system(＂pause＂); }
#于狄舍# 求两个数的最大公约数和最小公倍数的算法 - 作业帮
(17744202034)：[答案] 分别把两个数做质因数分解, 把相同质因数跳出来,取两者较小的次幂乘起来,就是最大公约数 两个数的积除以最大公约数,就是最小公倍数 比如说12和40 12=2^2*3 40=2^3*5 最大公约数=2^2=4 最小公倍数=12*40/4=120
#于狄舍# 如何用while循环求最大公约数算法:1)a除以b,得余数r; 2)如果r = 0,则停止:最大公约数是b; 3)否则,让a=b,让b=r,回到步骤一.实现这个算法并用它... - 作业帮
(17744202034)：[答案] 求最大公约数要用到辗转相除法,我不了解python语言,下面是用C写的,可基本原理都是一样的,希望有帮助. #include int main(void) { int m,r,n; int s; printf(＂input two numbers:\n＂); scanf(＂%d%d＂,&m,&n); s =m*n; while(n!=0) { r =m%n; m =n; ...
#于狄舍# 关于最大公约数的算法int gcd(int a,int b){ int t = 0; int c = 0; if(a==0) return b; if(b==0) return a; if(a { t=a; a=b; b=t; } c = a % b; while(c != 0) { a = b; b = c; c = a % ... - 作业帮
(17744202034)：[答案] 这是贪心算法.设最大公约数为X,则存在整数i,j使得:a = i*X,b = j*X又因为c = a % b 所以存在整数k使得:c = a-k*b = i*X - k*j*X = (i-j*k)*X即X也是c的公约数,然后a = b; b = c;如此循环,总有b = k*a的时侯,这时b...
#于狄舍# 整数的最大公约数怎么求?比如32和24 - 作业帮
(17744202034)：[答案] 算法思想:(最小公倍数=两个整数之积/最大公约数) (1) 对于已知两数m,n,使得m>n; (2) m除以n得余数r; (3) 若r=0,则n为求得的最大公约数,算法结束;否则执行(4); (4) m←n,n←r,再重复执行(2).
#于狄舍# 最大公约数的求法 -
(17744202034)： 72=2*2*2*3*380=2*2*2*2*590=2*3*3*5 所以72 80 90的最大公因数是:2 用短除法:也可以 给个好评吧
#于狄舍# 用自然语言描述求最大公约数的算法 -
(17744202034)： #include ＂stdio.h＂ long fun(long a,long b) { long i=a>b?b:a; //把a,b的最小值赋值给i do{ if(a%i==0&&b%i==0) break;//判断i能否被a,b整除,若能,结束循环;不能的话i-1再次判断……直到i同时能被a,b整除为止 }while(i--); return i; } void main()...
