C语言中怎么求最大公约数

一、什么是最大公约数

最大公约数（Greatest Common Divisor，简称GCD），又称最大公因子，是指两个或多个整数共有约数中最大的一个。即两个或多个整数公有的约数中最大的一个数。

二、求最大公约数的方法

求最大公约数的方法有辗转相除法、穷举法、质因数分解法等。

三、C语言求最大公约数实现

1、辗转相除法：

int gcd(int x, int y){int temp;if (x < y){temp = x;x = y;y = temp;}while (y != 0){temp = x % y;x = y;y = temp;}return x;}

2、穷举法：

int gcd(int x, int y){int i, gcd = 1;for (i = 1; i <= x && i <= y; i++){if (x % i == 0 && y % i == 0){gcd = i;}}return gcd;}

3、质因数分解法：

int gcd(int x, int y){int i, gcd = 1;for (i = 2; i <= x && i <= y; i++){while (x % i == 0 && y % i == 0){gcd *= i;x /= i;y /= i;}}return gcd;}