C语言求最大公约数代码

全栈程序员-站长 • 2026年3月20日上午9:44 • 未分类 • 阅读 2

题目：随机输入两个数，求其最大公约数

在此展示三种常用解题思路
1.首先展示第一种思路

#include  
     int main() { 
    int a,b,c; //先定义变量 printf("请输入：\n"); scanf("%d%d",&a,&b); //输入两个整型数字 if(a<b) { 
    c=a; a=b; b=c; //保证a≥b } int i = 0; for(i = b;i>0;i--) { 
    if(a%i == 0 && b%i == 0) { 
    printf("gcd(%d,%d) = %d\n",a,b,i); break; } } return 0; }

2.辗转相除法
这里涉及到一个公式：GCD(a,b) = GCD(b,a%b)

#include  
     int main() { 
    int a,b,c; printf("请输入："); scanf("%d%d",&a,&b); if(a<b) { 
    c = a; a = b; b = c; //确保a≥b } while(b != 0) { 
    c = b; b = a%b; //辗转相除：相比第一种思路大大提高了代码的效率 a = c; } printf("最大公约数为：%d",a); return 0; }

还有一种运用递归的思想

#include  
     int Gcd(int a,int b) { 
    if(a > b) { 
    if(a % b == 0) { 
    return b; } else { 
    return Gcd(b,a%b); } } else { 
    if(b % a == 0) { 
    return a; } else { 
    return Gcd(a,b%a); } } } int main() { 
    int a, b; int c = 0; printf("请输入两个整数："); scanf("%d%d",&a, &b); c = Gcd(a, b); printf("GCD（%d,%d）=%d\n",a,b,c); }

3.更相减损术
定义：(如果需要对分数进行约分，那么)可以折半的话，就折半(也就是用2来约分)。如果不可以折半的话，那么就比较分母和分子的大小，用大数减去小数，互相减来减去，一直到减数与差相等为止，用这个相等的数字来约分。

#include  
     main() { 
    int a,b; printf("请输入两个正整数："); scanf("%d%d",&a,&b); while(a%2==0) { 
    a/=2; } while(b%2==0) { 
    b/=2; } //让两个数都为奇数 while(a!=b) { 
    if(a>b) a=a-b; else b=b-a; //更相减损术：当差值等于减数的值时即为最大公约数 } printf("GCD=%d\n",a); return 0; }

本文结束，感谢阅览！

发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/201256.html原文链接：https://javaforall.net

C语言求最大公约数代码

题目：随机输入两个数，求其最大公约数

关于作者

全栈程序员-站长

发表回复

C语言求最大公约数代码

题目：随机输入两个数，求其最大公约数

关于作者

全栈程序员-站长

相关推荐

Linux通配符详解_Linux 通配符

Linux【实操篇】—— 日志管理

python中的ideavim有什么作用_IdeaVim插件施用技巧

WiFi 标准「建议收藏」

955 MCP+A2A 从0到1构建类Manus多Agent全栈应用

（超详细！！）Pytorch循环神经网络（RNN）快速入门与实战

发表回复