最大公約數演算法

㈠ 最大公約數怎麼求演算法

摘要 求最大公約數有多種方法，常見的有質因數分解法、短除法、輾轉相除法、更相減損法。如果有一個自然數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就是最大公約數。