最大公约数算法

㈠ 最大公约数怎么求算法

摘要 求最大公约数有多种方法，常见的有质因数分解法、短除法、辗转相除法、更相减损法。如果有一个自然数a能被自然数b整除，则称a为b的倍数，b为a的约数。几个自然数公有的约数，叫做这几个自然数的公约数。公约数中最大的一个公约数，称为这几个自然数的最大公约数。

㈡ 最大公约数二进制算法

WINDOWS自带计算机改为科学型,就能算2进制

㈢ 怎么计算两个数的最大公约数

把两个数分解质因数，看它人有哪些相同的质因数，这些相同的质因数的乘积就是这两个数的最大公约数。

最大公约数（Greatest Common Divisor，GCD），也称最大公因数（Highest Common Factor，HCF）、最大公因子，是一种数学概念，指两个或多个整数共有约数中最大的一个。

最大公约数的求解方法有质因数分解法、短除法、辗转相除法、更相减损法等，与其相对应的概念是最小公倍数。

如果数a能被数b整除，a就叫做b的 倍数，b就叫做a的 约数。约数和倍数都表示一个 整数与另一个整数的关系，不能单独存在。如只能说16是某数的倍数，2是某数的约数，而不能孤立地说16是倍数，2是约数。

"倍"与"倍数"是不同的两个概念，"倍"是指两个数相除的商，它可以是整数、 小数或者分数。"倍数"只是在数的 整除的范围内，相对于"约数"而言的一个数字的 概念，表示的是能被某一个自然数整除的数。
​

㈣ 求最大公约数有什么好算法吗

可以用辗转相除法

int cm(int a,int b)
{
if (!b) return a;
else return(cm(b,a %b));
}

㈤ 求解最大公约数的算法

先把每个数分解质因数，
再看有哪些质因数是每个数都有的，
这些质因数的乘积就是最大公约数。

㈥ 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的最大公约数

㈦ 如何用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;

}

㈧ 最大公约数的规律

辗转相除法

辗转相除法,又称欧几里德(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细菌数量达到稳定后的总个数.

这个题实质上就是要求两个数的最大公倍数,但是它用了更相减损术来描述,如果对更相减损术不了解的话第一思路只能模拟题目的描述;一旦我们看出是求最大公约数,我们便可以用辗转相除法来求解,大大提高解题效率!

辗转相除法和更相减损术在数学本质上是相同的,只是一个用的减法描述,另一个用的除法描述.显然,辗转相除法的逼近速率要快得多.

㈨ 最大公约数怎么算

看它们最大可以乘几，那就是最大公约数，最大公约数又名最大公因数，

㈩ 关于最大公约数的算法

这是贪心算法。
设最大公约数为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就是最大公约数。