利用辗转相除法——求最大公约数（详解）_辗转相除法求最大公约数

辗转相除法

求最大公约数：
给定两个数，求这两个数的最大公约数

欧几里得算法又称辗转相除法，是指用于计算两个非负整数a，b的最大公约数。应用领域有数学和计算机两个方面。计算公式gcd(a,b) = gcd(b,a mod b)。

例如：假如需要求 100 和18 两个正整数的最大公约数,用欧几里得算法，是这样进行的：
100 / 18 = 5 (余 10)
18 / 10= 1(余8)
10 / 8 = 1(余2)
8 / 2 = 4 (余0)
至此，最大公约数为2
以除数和余数反复做除法运算，当余数为 0 时，取当前算式除数为最大公约数，所以就得出了 100 和 18 的最大公约数2。

//最大公约数
//给定两个数，求这两个数的最大公约数
#include<stdio.h>
int Fac(int a, int b)
{
	int d = 1;
	int c = 0;
	while (d)
	{
		c = a / b;
		d = a % b;
		a = b;
		b = d;
	}
	return a;
}
int main()
{
	int a = 0;
	int b = 0;
	int ret = 0;
	printf("请输入两个数字：\n");
	scanf("%d %d", &a, &b);
	if (a>b)
	{
		ret=Fac(a, b);
	}
	else
	{
		ret = Fac(b, a);
	}
	printf("最大公约数：%d\n", ret);
	return 0;
}

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

辗转相除法求解最大公约数并不是唯一的方式，但是却相当简便！