求最大公约数有多种方法，接下来我对辗转相除法、更相减损法分别做介绍。
辗转相除法： gcd(a,b) = gcd(b,a mod b)。
假如，需要求 1997 和 615 两个正整数的最大公约数,用辗转相除法，是这样进行的：
1997 / 615 = 3 (余 152)
615 / 152 = 4(余7)
152 / 7 = 21(余5)
7 / 5 = 1 (余2)
5 / 2 = 2 (余1)
2 / 1 = 2 (余0)
至此，最大公约数为1
以除数和余数反复做除法运算，当余数为 0 时，取当前算式除数为最大公约数，所以就得出了 1997 和 615 的最大公约数 1。
更相减损法：
举例：
例1：用更相减损术求98与63的最大公约数。（一奇一偶）
解：由于63不是偶数，把98和63以大数减小数，并辗转相减：
98-63=35
63-35=28
35-28=7
28-7=21
21-7=14
14-7=7
所以，98和63的最大公约数等于7。
例2、用更相减损术求260和104的最大公约数。（两个偶数)
解：由于260和104均为偶数，首先用2约简得到130和52，再用2约简得到65和26。
此时65是奇数而26不是奇数，故把65和26辗转相减：
65-26=39
39-26=13
26-13=13
所以，260与104的最大公约数等于13乘以第一步中约掉的两个2，即1322=52。
代码实现如下：
#include<stdio.h>//辗转相除法int gcd1(int x, int y){//判断x/y余数是否为0int z = x % y;//直到余数为0，则跳出循环while(z){//循环过程中，将除数给x，余数给y，求新的余数zx = y;y = z;z = x % y;}//除数y为最大公约数return y;}//更相减损术int gcd2(int x, int y){int sum1 = 1;//先判断 x y是否都是偶数while ((x % 2 == 0) && (y % 2 == 0)){sum1 *= 2;x = x / 2;y = y / 2;}while (1){//保证，被减数大于减数，不然就交换顺序if (x < y){int temp = x;x = y;y = temp;}//差放在s中int s = x - y;//判断差 和 减数 是否相等，如果是，跳出循环。if (y == s)break;else{x = y;y = s;}}//最大公约数就是约掉的若干个2的积与第二步中等数（减数=差）的乘积return y * sum1;}int main(){int a = 98;int b = 63;int max1 = gcd1(a, b);int max2 = gcd2(a, b);printf("%d %d的最大公约数为 %dn", a, b, max1);printf("%d %d的最大公约数为 %dn", a, b, max2);return 0;}