最大公约数，也称最大公因数、最大公因子，指两个或多个整数共有约数中最大的一个。求解的方式比较多，暴力穷举、辗转相除法、更相减损法、Stein算法。 1.暴力穷举法 如果大数可以整除小数，那么最大公约数为小数。如果不能整除小数，那么这两个数就按大到小依次对比小数小的数求余，遇到都能够整除的，就是最大公约数。
#include<stdio.h> #include<windows.h> #pragma warning(disable:4996) int main(){ //暴力穷举法 int a = 0; int b = 0; printf("请输入两个整数:"); scanf("%d%d", &a, &b); if (a >= b){ int i = 0; for (i = b; i >= 1; i--){ if (a%i == 0 && b%i == 0){ printf("最大公约数为：%d\n", i); break; } } } else{ int j = 0; for (j = a; j >= 1; j--){ if (a%j == 0 && b%j == 0){ printf("最大公约数为：%d\n", j); break; } } } system("pause"); return 0; }2.辗转相除法 用大数对小数求余，若余数为0，则除数为最大公约数。若余数不为0，将此余数作为除数，小数作为被除数，重新求余，直到余数为0为止。此时的最大公约数为余数。
#include<stdio.h> #include<windows.h> #pragma warning(disable:4996) int main(){ int a = 0; int b = 0; printf("请输入两个整数:"); scanf("%d%d", &a, &b); if (a >= b){ int c = a%b; while (c != 0){ a = b; b = c; c = a%b; } printf("最大公约数为：%d\n",b); } else{ int d = b%a; while (d != 0){ b = a; a = d; d = b%a; } printf("最大公约数为：%d\n", a); } system("pause"); return 0; }3.更相减损法 当两个数相等时，最大公约数为他们其中任意一个；当两个数不相等时，用大数减小数得到的差和之前的那个小数再次相减，直到两个数相等，相等的两个中，任意一个都是最大公约数。
#include<stdio.h> #include<windows.h> #pragma warning(disable:4996) int main(){ //更相减损法 int a = 0; int b = 0; printf("请输出两个整数:"); scanf("%d%d", &a, &b); while ((a - b)!=0){ if (a > b){ a = a - b; } else{ b = b - a; } } printf("最大公约数为：%d\n", b); system("pause"); return 0; }4.Stein算法 步骤： step1：两数均为偶数时将其同时除以2至至少一数为奇数为止，记录除掉的所有公因数2的乘积k； step2：如果仍有一数为偶数，连续除以2直至该数为奇数为止； step3：用更相减损法(辗转相减法)，即GCD(a,b)=GCD(a-b,b)，或辗转相除法求出两奇数的最大公约数d； step4：原来两数的最大公约数即为d*k。
#include<stdio.h> #include<windows.h> #pragma warning(disable:4996) int main(){ //Stein算法 int a = 0; int b = 0; printf("请输入两个整数:"); scanf("%d%d", &a, &b); int gcd = 0; int k = 1; while ((!(a & 1)) && (!(b & 1))){ //step1; k <<= 1; //用k记录全部公因子2的乘积 ； a >>= 1; b >>= 1; } while (!(a & 1))a >>= 1; //step2; while (!(b & 1))b >>= 1; if (a<b) a ^= b, b ^= a, a ^= b; //交换，使a为较大数； while (a != b){ //step3; a -= b; if (a<b) a ^= b, b ^= a, a ^= b; } gcd = k*a; printf("最大公约数为：%d\n", gcd); system("pause"); return 0; }