輾轉相除法求最大公約數

一、輾轉相除法（歐幾里得算法）1、定義：所謂輾轉相除法，就是對於給定的兩個數，用較大的數除以較小的數。若餘數不爲零，則將餘數和較小的數構成新的一對數，繼續上面的除法，直到大數被小數除盡，則這時較小的數就是原來兩個數的最大公約數。

最大公約數與最小公倍數的求解是很多初學C的人所面臨的一個問題，接下來爲大家提供方法。

問題：

請從鍵盤上輸入兩個數值 x，y，請用C語言求出這兩個數值的最大公約數與最小公倍數。

int divisor (int a,int b) /*自訂函數求兩數的最大公約數*/ { int temp; /*定義整型變量*/ if(a

最大公因數；也稱最大公約數、最大公因子，指兩個或多個整數共有約數中最大的一個。

#include void main(){int m,n,k;scanf("%d%d",&m,&n);while(n) {k=m%n;m=n;n=k;}printf("%d",m);}

最小公倍數：兩個或多個整數公有的倍數叫做它們的公倍數。

舉個例子你就懂了： 用輾轉相除法或更相減損術求324,243,135的最大公約數 先求兩個較大數324與243的最大公約數 324/243=181 243/81=3 知324與243的最大公約數是81 或 324-243=81 243-81=162 162-81=81 知324與243的最大公約數是81 再求81與較

輾轉相除法

又名歐幾里德算法（Euclidean algorithm），它是已知最古老的算法， 其可追溯至公元前300年前。輾轉：望文生義，就是翻來覆去。相除就很好理解了，就是進行除法運算。輾轉相除法的核心就是不斷的讓兩個數做除法運算。其原理基於兩個整數的最大公約數等於其中較小的數和兩數的相除餘數的最大公約數。假設兩數爲 x，y。先令 z = x % y ；之後 y 賦給 x 即令x = y ；再將 z 賦給 y 即令y = z；輾轉相減，其終止條件爲：y 等於0時。

輾轉相除法，是求兩個正整數之最大公因子的算法。 輾轉相除法的算法過程如下：設兩數爲a、b(a>b)，求a和b最大公約數(a，b)的步驟如下：用a除以b，得 a÷b=q，餘數r1(0≤r1)。若r1=0，則(a，b)=b；若r1不等於0，則再用b除以r1，得b÷r1=q，餘數r2 (0

代碼如下：

輾轉相減法

即尼考曼徹斯法，其特色是做一系列減法，從而求得最大公約數。輾轉相減法即透過對兩數的不斷減法運算。假設兩數爲 x, y。當 x > y 時，令 x = x - y；反之，則令 y = y - x；之後一直輾轉相減，直至 x = y 時，終止。

輾轉相除法求兩個數a和b的最大公約程序如下： 程式解析如下： 設兩數爲a、b(b1），則m=kn+xd=kyd+xd=(ky+x)d，則a=mc=(ky+x)dc，b=nc=ycd，故a與b最大公約數成爲cd，而非c】 從而可知(b,r)=c，繼而(a,b)=(b,r）。 證畢。 擴展資料VB語

代碼如下：

窮舉法

窮舉法的基本思想是根據題目的部分條件確定答案的大致範圍，並在此範圍內對所有可能的情況逐一驗證，直到全部情況驗證完畢。窮舉法又稱枚舉法，透過對數值範圍內的所有數字進行檢驗，得出其結果。

可用遞歸來求。 推薦以下代碼： #includeint (int a,int b) //求最大公約數函數{if (a%b==0) return b;else return (b,a%b); //輾轉相除法}void main(){int a,b;scanf("%d%d",&a,&b);printf("%dn",(a,b));}

代碼如下：

擴展閱讀，以下內容您可能還感興趣。

輾轉相除法爲什麼能求最大公約數

可以維基、百度百科，

簡單來說，被除數被分成了兩坨，一坨可以被整除，一坨是餘數，現在都可以被整除的玩意必然也可以被最後的最大公約數整除，所以只用找餘數與除數的最大公因數，然後同理，餘數與除數又分別成了被除數和除數，直至最後整除

編程一個C語言程序,輸入兩個數,採用輾轉相除法來計算最大公約數

可以參考下面的代碼：

#include <stdio.h>

int main()

{

int m, n, r;

scanf ("%d%d", &m, &n);

if (m>n){r=m, m=n, n=r;}

r=n%m;

while (r!=0){

n = m;

m = r;

r = n%m;

}

printf ("%dn", m);

return 0;

}

擴展資料：

函數 scanf() 是從標準輸入流stdin(標準輸入設備，一般指向鍵盤)中讀內容的通用子程序，可以說明的格式讀入多個字元，並儲存在對應地址的變量中。

函數的第一個參數是格式字元串，它指定了輸入的格式，並按照格式說明符解析輸入對應位置的資訊並存儲於可變參數列表中對應的指針所指位置。每一個指針要求非空，並且與字元串中的格式符一一順次對應。

參考資料來源：百度百科-scanf （計算機語言函數）

參考資料來源：百度百科-while （循環語句及英文單詞）

c語言用輾轉相除法求最大公約數

你沒發圖我不知道你的程序有什麼問題，給出我的代碼：#include<stdio.h>

int *(int a,int b){

return a%b?*(b,a%b):b; 

} 

int main(){

printf("%d",*(4,6));

return 0;

}

執行結果：更多追問追答追問不好意思，忘記發圖了追答看不清。。追問哦哦，我已經知道自己錯哪了，但是不知道爲什麼錯#include

int main()

{

int a,b,rem;

int *;

printf("Enter 2 integers:");

scanf("%d,%d",&a,&b);

....

}

執行時我輸入a和b中間用的是空格，而不是逗號，所以錯了，但是爲什麼是個負數呢。。。我輸入125 45

然後結果是－5應該是5纔對啊

爲啥輾轉相除法可以求最大公約數

輾轉相除法求最大公約數原理：

設兩數爲a、b(a>b)，用*(a,b)表示a，b的最大公約數，r=a (mod b) 爲a除以b的餘數，k爲a除以b的商，即a÷b=k.......r。輾轉相除法即是要證明*(a,b)=*(b,r)。

第一步：令c=*(a,b)，則設a=mc，b=nc

第二步：根據前提可知r =a-kb=mc-knc=(m-kn)c

第三步：根據第二步結果可知c也是r的因數

第四步：可以斷定m-kn與n互質(假設m-kn=xd，n=yd (d>1)，則m=kn+xd=kyd+xd=(ky+x)d，則a=mc=(ky+x)cd，b=nc=ycd，則a與b的一個公約數cd>c，故c非a與b的最大公約數，與前面結論矛盾)，因此c也是b與r的最大公約數。

從而可知*(b,r)=c，繼而*(a,b)=*(b,r)。

證畢。

以上步驟的操作是建立在剛開始時r≠0的基礎之上的。即m與n亦互質。

給我講一下用短除法和輾轉相除法求最大公約數

輾轉相除法：

要求a、b兩個整數的最大公約數，a＞b，那麼我們先用a除以b，得到商 q1，餘數r1：a÷b＝q1…r1我們當然也可以把上面這個式子改寫成乘法式：

a＝b * q1＋r1

如果r1＝0，那麼b就是a、b的最大公約數3。要是r1≠0，就繼續除，用b除以r1，我們也可以有和上面一樣的式子：

b＝r1q2＋r2

如果餘數r2＝0，那麼r1就是所求的最大公約數3。因爲如果b＝r1q2＋r2變成了b＝r1q2，那麼b1r1的公約數就一定是a1b的公約數。這是因爲一個數能同時除盡b和r1，那麼由a＝b * q1＋r1，就一定能整除a，從而也是a1b的公約數。

反過來，如果一個數d，能同時整除a1b，那麼由1）式，也一定能整除r1，從而也有d是b1r1的公約數。

這樣，a和b的公約數與b和r1的公約數完全一樣，那麼這兩對的最大公約數也一定相同。那b1r1的最大公約數，在r1＝0時，不就是r1嗎？所以a和b的最大公約數也是r1了。

如果r2不是0，用r1除以r2，……直到餘數爲零爲止。

短除法

如例子：

2|_18__30__

3|_9__15__

3 5

其實短除法就是放到一起慢慢約分，對於簡單的還有效，而大一點的數還是輾轉相除法比較有效，而且輾轉相除法的邏輯性也爲計算機編程提供了條件