题目
给定两个数，求这两个数的最大公约数
例如：
输入：20 40
输出：20
解题思路
最大公约数：即两个数据中公共约数的最大者
求解的方式比较多，暴力穷举、辗转相除法、更相减损法、Stein算法算法
方法一：辗转相除法（推荐此方法）
思路：
例子：18和24的最大公约数
第一次：a = 18 b = 24 c = a%b = 18%24 = 18
循环中：a = 24 b=18
第二次：a = 24 b = 18 c = a%b = 24%18 = 6
循环中：a = 18 b = 6
第三次：a = 18 b = 6 c = a%b = 18%6 = 0
循环结束
此时b中的内容即为两个数中的最大公约数
#include
int main()
{
int m = 0;
int n = 0;
int tmp = 0;
printf("请输入两个整数: ");
scanf("%d %d", &m, &n);
while (tmp = m % n)
{
m = n;
n = tmp;
}
printf("最大公约数为:%d\n", n);
return 0;
}
方法二：暴力穷举法
如果大数可以整除小数，那么最大公约数为小数。
如果不能整除小数，那么这两个数就按大到小依次对比小数小的数求余，遇到都能够整除的，就是最大公约数。
#include
#include
#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;
}
方法三：更相减损法
当两个数相等时，最大公约数为他们其中任意一个；
当两个数不相等时，用大数减小数得到的差和之前的那个小数再次相减，直到两个数相等，相等的两个中，任意一个都是最大公约数。
#include
#include
#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;
}
方法四：Stein算法
步骤：
step1：两数均为偶数时将其同时除以2至少一数为奇数为止，记录除掉的所有公因数2的乘积k；
step2：如果仍有一数为偶数，连续除以2直至该数为奇数为止；
step3：用更相减损法(辗转相减法)，即GCD(a,b)=GCD(a-b,b)，或辗转相除法求出两奇数的最大公约数d；
step4：原来两数的最大公约数即为d*k。
#include
#include
#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 while (a != b){ //step3; a -= b; if (a } gcd = k*a; printf("最大公约数为：%d\n", gcd); system("pause"); return 0; }