【C语言】实现求两个数的最大公约数【四种算法】 | 您所在的位置:网站首页 › c语言问题例子 › 【C语言】实现求两个数的最大公约数【四种算法】 |
题目
给定两个数,求这两个数的最大公约数 例如: 输入: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; b >>= 1; } while (!(a & 1))a >>= 1; //step2; while (!(b & 1))b >>= 1; if (a |
CopyRight 2018-2019 实验室设备网 版权所有 |