辗转相除法
**//C的代码实现很简洁递归**
int GCD(int a,int b)
{
return b==0?a:GCD(b,a%b);
}
**//JAVA和PYTHON都感觉是很流利的BCYY**
public static int gcd(int m, int n)
{
while (true)
{
if ((m = m % n) == 0)
return n;
if ((n = n % m) == 0)
return m;
}
}
///
#递归解决最大公约数问题
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
辗转相除法， 又名欧几里德算法（Euclidean algorithm），是求最大公约数的一种方法。它的具体做法是：用较大数除以较小数，再用出现的余数（第一余数）去除除数，再用出现的余数（第二余数）去除第一余数，如此反复，直到最后余数是0为止。如果是求两个数的最大公约数，那么最后的除数就是这两个数的最大公约数。
另一种求两数的最大公约数的方法是更相减损法。
中文名 辗转相除法 外文名 Euclidean algorithm 别 称 欧几里德算法 用 途 求最大公约数 归属学科 数学 出现书目 《几何原本》
基本原理编辑
两个数的最大公约数是指能同时整除它们的最大正整数。 [1]
设两数为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亦互质。 [1]
算法描述编辑
用辗转相除法确定两个正整数 a 和 b(a≥b) 的最大公因数 ：
当 时， ；否则 递归或循环运算得出结果。
算法流程图如下：
伪代码描述如下：
1
2
3
4
5
6
7
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语言
1
2
3
4
5
6
7
int GCD(int a,int b)
{
return b==0?a:GCD(b,a%b);
}
C++语言实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#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#语言实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
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实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
INPUT m,n
DO
r=m MOD n
m=n
n=r
LOOP UNTIL r=0
PRINT m
END
Pascal实现
1
2
3
4
5
6
7
8
9
10
11
function gcd(a,b:integer):integer;
begin
if b=0 then
gcd:=a
else
gcd:=gcd(b,a mod b);
end;
Java 实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
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实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#递归解决最大公约数问题
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