最大公约数算法
Ⅰ 怎么计算两个数的最大公约数
把两个数分解质因数，看它人有哪些相同的质因数，这些相同的质因数的乘积就是这两个数的最大公约数。
最大公约数（Greatest Common Divisor，GCD），也称最大公因数（Highest Common Factor，HCF）、最大公因子，是一种数学概念，指两个或多个整数共有约数中最大的一个。
最大公约数的求解方法有质因数分解法、短除法、辗转相除法、更相减损法等，与其相对应的概念是最小公倍数。
如果数a能被数b整除，a就叫做b的 倍数，b就叫做a的 约数。约数和倍数都表示一个 整数与另一个整数的关系，不能单独存在。如只能说16是某数的倍数，2是某数的约数，而不能孤立地说16是倍数，2是约数。
"倍"与"倍数"是不同的两个概念，"倍"是指两个数相除的商，它可以是整数、 小数或者分数。"倍数"只是在数的 整除的范围内，相对于"约数"而言的一个数字的 概念，表示的是能被某一个自然数整除的数。
Ⅱ 最大公约数怎么算
看它们最大可以乘几，那就是最大公约数，最大公约数又名最大公因数，
Ⅲ 最大公约数的规律
辗转相除法
辗转相除法,又称欧几里德(Euclid)算法,是欧几里德在约公元前300年提出的.
用辗转相除法求两个数的最大公约数的步骤如下：
先用小的一个数除大的一个数，得第一个余数；
再用第一个余数除小的一个数，得第二个余数；
又用第二个余数除第一个余数，得第三个余数；
这样逐次用后一个数去除前一个余数，直到余数是0为止。那么，最后一个除数就是所求的最大公约数（如果最后的除数是1，那么原来的两个数是互质数）。
辗转相除法是求两个数的最大公约数的方法。如果求几个数的最大公约数，可以先求两个数的最大公约数，再求这个最大公约数与第三个数的最大公约数。这样依次下去，直到最后一个数为止。最后所得的一个最大公约数，就是所求的几个数的最大公约数。
这个思想的一般数学公式可以表示为:
gcd(a,b)=gcd(b,a mod b)
注: 函数gcd(x,y)表示x和y的最大公约数,(Greatest Common Diviser);运算x mod y表示x除y的余数,在C语言中可以表示为x % y;
简单地描述为:a,b地最大公约数,等于b与a除b的余数的最大公约数
分享一个很精炼的函数
int gcd(int a,int b){
while(a>b?(a=a%b):(b=b%a));
return a+b;
}
在收集资料的过程中,我还发现一些有意思的东西~~
最小公倍数
公式可以描述为:
lcm(a,b)*gcd(a,b)=a*b
注:函数LCM(x,y)表示x,y的最小公倍数(Least Common Multiply);函数gcd(x,y)表示x,y的最大公约数;
通过这个公式我们知道,要求a,b的最小公倍数,只需求出a,b的最大公约数,然后套用公式,即可求出最小公倍数
这个公式稍微想一下是很好理解的
更相减损术
我国早期也有求最大公约数的算法,就是"更相减损术".在<九章算术>中有更相减损术的步骤:
可半者半之,不可半者副置分母`子之数,以少减多,更相减损,求其等也,以等数约之.
翻译:1.任意给出两个正整数;判断它们是否都是偶数.若是,用2约简;若不是,执行第二步.
2.以较大的数减去较小的数,接着把较小的数与所得的差比较,并以大数减小数.继续这个操作,直到所得的数相等为止,则这个数(等数)就是所求的最大公约数.
我曾经看到过一个练习题就是用更相减损术描述的,大意是这样:
Q博士在实验室培养一批细菌.他发现他的细菌中有两种相互制约的细菌A和B.于是他培养这两种细菌,在试验中他发现细菌A,B有如下规律:当AB细菌共存时,细菌A,B中数量少的那一方每天会吞噬掉数量多的一方的部分个体,吞噬的数量等于数量少一方的个体数量;这样培养下去,直到A,B细菌数量相等时,便不再相互吞噬.
程序要求任意输入两个数a,b分别代表细菌A,B的数量;程序要求输出AB细菌数量达到稳定后的总个数.
这个题实质上就是要求两个数的最大公倍数,但是它用了更相减损术来描述,如果对更相减损术不了解的话第一思路只能模拟题目的描述;一旦我们看出是求最大公约数,我们便可以用辗转相除法来求解,大大提高解题效率!
辗转相除法和更相减损术在数学本质上是相同的,只是一个用的减法描述,另一个用的除法描述.显然,辗转相除法的逼近速率要快得多.
Ⅳ 最大公约数二进制算法
WINDOWS自带计算机改为科学型,就能算2进制
Ⅳ 3个数最大公约数算法
对于3个数A，B，C，最小公倍数=A*B*C/最小公约数的平方
对于对小公约数，可以采用两次辗转相除法
先求A，B的最小公约数D
再求出C与D的最小公约数E
那么E就是这三个数的最小公约数
A*B*C/E/E就是三个数的最小公倍数
举例如下
求1734,816和1343的最大公约数：
首先求1734,816的最大公约数：
gcd(1734,816)表示开始求1734,816的最大公约数。
gcd(1734,816)
=gcd(1734,816)1734=2*816+102
（102为1734除以816的余数，而2为商，以后的如此类推）
=gcd(816，102)816=8*102
（至此余数为0，则102为1734和816的最大公约数）
运用3个数的最大公约数的求解原理：
只需求的1343和102的最大公约数即为1734,816和1343的最大公约数。
gcd(1343，102)
=gcd(1343，102)1343=13*102+17
=gcd(102，17)102=6*17
（至此余数为0，则17为即为1734,816和1343的最大公约数）
则17为即为1734,816和1343的最大公约数
更相减损术求解（也是现学现卖的）
原理：
第一步：任意给定两个正整数；判断它们是否都是偶数。若是，则用2约简；若不是则执行第二步。
第二步：以较大的数减较小的数，接着把所得的差与较小的数比较，并以大数减小数。继续这个操作，直到所得的减数和差相等为止，则这个等数就是所求的最大公约数。
其中所说的“等数”，就是最大公约数。求“等数”的办法是“更相减损”法，实际上就是辗转相除法。
首先看1734和816.
两个数都是偶数，为了简化计算，都除以2得到867和408.
下面是计算过程：
867-408=459
459-408=51
408-51=357
357-51=306
306-51=255
255-51=204
204-51=153
153-51=102
102-51=51
至此所得的减数和差相等，由于867和408是1734和816除以2得到的数字。故
1734和816的最大公约数还是102（51*2=102）.
在用更相减损术求102和1343的的最大公约数即为1734,816和1343的最大公约数。
1343-102=1241(由于102*10=1020,1343-1020=323,323还是大于102的）
...
...
...
323-102=221
221-102=119
119-102=17
102-17=85
85-17=68
68-17=51
51-17=34
34-17=17
至此所得的减数和差相等.故17为1734,816和1343的最大公约数
Ⅵ 求解最大公约数的算法
先把每个数分解质因数，
再看有哪些质因数是每个数都有的，
这些质因数的乘积就是最大公约数。
Ⅶ 关于最大公约数的算法
这是贪心算法。
设最大公约数为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就是最大公约数。
Ⅷ 最大公约数怎么算
质因数分解法：把每个数分别分解质因数，再把各数中的全部公有质因数提取出来连乘，所得的积就是这几个数的最大公约数。
短除法：短除法求最大公约数，先用这几个数的公约数连续去除，一直除到所有的商互质为止，然后把所有的除数连乘起来，所得的积就是这几个数的最大公约数。
最大公因数，也称最大公约数、最大公因子，指两个或多个整数共有约数中最大的一个。a，b的最大公约数记为（a，b），同样的，a，b，c的最大公约数记为（a，b，c），多个整数的最大公约数也有同样的记号。求最大公约数有多种方法，常见的有质因数分解法、短除法、辗转相除法、更相减损法。与最大公约数相对应的概念是最小公倍数，a，b的最小公倍数记为[a，b]。
如果数a能被数b整除，a就叫做b的倍数，b就叫做a的约数。约数和倍数都表示一个整数与另一个整数的关系，不能单独存在。如只能说16是某数的倍数，2是某数的约数，而不能孤立地说16是倍数，2是约数。
"倍"与"倍数"是不同的两个概念，"倍"是指两个数相除的商，它可以是整数、小数或者分数。"倍数"只是在数的整除的范围内，相对于"约数"而言的一个数字的概念，表示的是能被某一个自然数整除的数。
几个整数中公有的约数，叫做这几个数的公约数；其中最大的一个，叫做这几个数的最大公约数。例如：12、16的公约数有1、2、4，其中最大的一个是4，4是12与16的最大公约数，一般记为（12，16）=4。12、15、18的最大公约数是3，记为（12，15，18）=3。
几个自然数公有的倍数，叫做这几个数的公倍数，其中最小的一个自然数，叫做这几个数的最小公倍数。例如：4的倍数有4、8、12、16，……，6的倍数有6、12、18、24，……，4和6的公倍数有12、24，……，其中最小的是12，一般记为[4，6]=12。12、15、18的最小公倍数是180。记为[12，15，18]=180。若干个互质数的最小公倍数为它们的乘积的绝对值。
Ⅸ 如何用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;
}
Ⅹ 求最大公约数有什么好算法吗
可以用辗转相除法
int cm(int a,int b)
{
if (!b) return a;
else return(cm(b,a %b));
}