輾轉相除法:基本原理,證明,算法描述,示例,例1,例2,代碼實現,c語言,C++語

輾轉相除法，又名歐幾里德算法（Euclidean algorithm），是求最大公約數的一種方法。它的具體做法是：用較大數除以較小數，再用出現的餘數（第一餘數）去除除數，再用出現的餘數（第二餘數）去除第一餘數，如此反覆，直到最後餘數是0為止。如果是求兩個數的最大公約數，那么最後的除數就是這兩個數的最大公約數。

另一種求兩數的最大公約數的方法是更相減損法。

基本介紹

中文名：輾轉相除法
外文名：Euclidean algorithm
別稱：歐幾里德算法
用途：求最大公約數
歸屬學科：數學
出現書目：《幾何原本》

基本原理,證明,算法描述,示例,例1,例2,代碼實現,c語言,C++語言實現,C#語言實現,Basic實現,Pascal實現,Java 實現,Python實現,

基本原理

兩個數的最大公約數是指能同時整除它們的最大正整數。

設兩數為a、b(a≥b)，求a和b最大公約數

的步驟如下：

(1)用a除以b(a≥b)，得

。

(2)若

，則

；

(3)若

，則再用b除以

，得

(4)若

，則

；若

，則繼續用

除以

，......，如此下去，直到能整除為止。

其最後一個餘數為0的除數即為

的最大公約數。

證明

設兩數為a、b(a>b)，用

表示a，b的最大公約數，r=a (mod b) 為a除以b的餘數，k為a除以b的商，即

。輾轉相除法即是要證明

。

第一步：令

，則設

第二步：根據前提可知

第三步：根據第二步結果可知，

也是

的因數

第四步：可以斷定

與

互質（這裡用反證法進行證明：設

，則

，則a與b的一個公約數

，故c非a與b的最大公約數，與前面結論矛盾，因此c也是b與r的最大公約數）從而可知

，繼而

。

證畢

註：以上步驟的操作是建立在剛開始時

的基礎之上的，即m與n亦互質。

算法描述

用輾轉相除法確定兩個正整數 a 和 b(a≥b) 的最大公因數

：

當

時，

；否則

遞歸或循環運算得出結果。

算法流程圖如下：

偽代碼描述如下：

function gcd(a,b) {if b< >0        return gcd(b,a mod b);else        return a；}

示例

例1

123456 和 7890 的最大公因數是 6，這可由下列步驟（其中，“a mod b”是指取 a ÷ b 的餘數）看出：

a	b	a mod b
123456	7890	5106
7890	5106	2784
5106	2784	2322
2784	2322	462
2322	462	12
462	12	6
12	6	0

例2

已知不定方程為

，利用輾轉相除法求出一組整數解

解：求

的算式為：

所以

即

所以

是不定方程

的一組解。

代碼實現

c語言

int GCD(int a,int b){    return b==0?a:GCD(b,a%b);}

C++語言實現

#include<iostream>using namespace std;int a , b , a1 , b2 , l;int gcd(int x , int y){    if(!y)       return x;else         return gcd(y , x%y); }int main(){cout << "請輸入兩個正整數，計算它們的最大公約數" << endl ;int a , b , ans;cin >> a >> b;if(a > b)ans = gcd(a , b);else     ans = gcd(b , a);cout << ans;return 0;}

C#語言實現

static int sucDivison(int m, int n)　/*除法*/{　int remainder = 0;　if (m % n == 0)　    {　return n;　}　else　    {　        do　        {　            remainder = m % n;　            m = n;　            n = remainder;　        } while (remainder > 0);　}　if (n == 0)　{　return m;　}　return n;　}

Basic實現

INPUT m,n DO r=m MOD nm=nn=rLOOP UNTIL r=0PRINT mEND

Pascal實現

function gcd(a,b:integer):integer;begin    if b=0 then         gcd:=a    else         gcd:=gcd(b,a mod b);end;

Java 實現

public static int gcd(int m, int n) {    while (true)     {    if ((m = m % n) == 0)        return n;        if ((n = n % m) == 0)            return m;}}

Python實現

#遞歸解決最大公約數問題def gcd(x , y):       if y == 0         return x     else gcd(y, x%y)   x = int(input('請輸入第一個數字：'))y = int(input('請輸入第二個數字：'))print('%d 和 %d 的最大公約數為：' %(x,y),gcd(x,y))#非遞歸def gcd(x, y):    while y:            x, y = y, x%y    return x

輾轉相除法