C语言辗转相除法求2个数的最小公约数_网络技术

C语言辗转相除法求2个数的最小公约数

发布时间 - 2026-01-10 22:05:08 点击率：次

辗转相除法最大的用途就是用来求两个数的最大公约数。

用（a,b）来表示a和b的最大公约数。

有定理：已知a,b,c为正整数，若a除以b余c，则（a,b）=(b,c)。（证明过程请参考其它资料）

例：求 15750 与27216的最大公约数。

解：

∵27216=15750×1+11466 ∴（15750，27216）=（15750，11466）
∵15750=11466×1+4284 ∴（15750，11466）=(11466,4284)
∵11466=4284×2+2898 ∴(11466,4284)=（4284，2898）
∵4284=2898×1+1386   ∴（4284，2898）=（2898，1386）
∵2898=1386×2+126   ∴（2898，1386）=（1386，126）
∵1386=126×11     ∴（1386，126）=126

所以（15750，27216）=126

辗转相除法比较适合用来求两个比较大的数的最大公约数。

代码如下：

#include<stdio.h>
int main()
{
  int a,b,temp,x;
  scanf("%d%d",&a,&b);
  if(a>b)
  {
    temp=b;
    b=a;
    a=temp;
  }
  while(b%a!=0)
  {
    x=b%a;
    b=a;
    a=x;
  }
  printf("%d",a);
}

以上所述是小编给大家介绍的C语言辗转相除法求2个数的最小公约数，希望对大家有所帮助，如果大家有任何疑问请给我留言，小编会及时回复大家的。在此也非常感谢大家对网站的支持！

# c语言最小公约数 # C语言实现求最大公约数的三种方法 # C语言实现求解最小公倍数的算法示例 # C语言之实现辗转相除法的两种方式 # 小编 # 在此 # 给大家 # 比较大 # 所述 # 给我留言 # 请参考 # 感谢大家 # 疑问请 # 有任何 # 正整数 # br # nbsp # pre # temp # main # int # printf # amp # scanf

相关栏目：【网站优化151355 】【网络推广146373 】【网络技术251813 】【 AI营销90571 】

上一篇：海尔专卖店2026年要进行四个变革

下一篇：制作钓鱼网站视频教程,如何识别钓鱼网站？

相关栏目网站优化
网络推广
网络技术
AI营销

最新文章 Sublime怎么一键压缩JS代码 Su sublime如何在搜索中使用正则表达式 Sublime如何设置透明窗口效果 Su mysql如何设计商品表结构_mysql css属性背景图不显示怎么办_通过检查路如何使用Golang实现排序_Golan 农历闰月是怎么回事_为合回归年加一月调整塑造《刺客信条》艾吉奥传奇的编剧离开育碧 1英里等于多少公里 1mile和km的换 css grid布局中行和列是如何定义的 PS批量旋转和翻转图片，快速校正图片方向 C# Swagger UI自定义方法 C OPPO手机九宫格和全键盘怎么切换_OP Go语言如何实现用户登录注册_Golan 1节飞行速度多少公里每小时 1节是多少公纸嫁衣8千子树第五章庙门怎么开启庙门 Laravel 多行数据编辑表单中实现逐明日之后如何提升钓鱼等级明日之后提升钓支付宝怎样查年度账单_支付宝年度账单查看 C# 多线程UI更新Dispatcher

上一篇：海尔专卖店2026年要进行四个变革

下一篇：制作钓鱼网站视频教程,如何识别钓鱼网站？