最大公約數演算法
Ⅰ 怎麼計算兩個數的最大公約數
把兩個數分解質因數，看它人有哪些相同的質因數，這些相同的質因數的乘積就是這兩個數的最大公約數。
最大公約數（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));
}