nian念不忘
2021-08-07 00:59
采纳率: 100%
浏览 50

C语言 求两个数的最小公倍数、最大公约数

这是练习上的一题,答案是第一张图片上的,我想到的是第二张图片上的
不明白为什么要两个数取余,在替换,为什么要这样想,
求解释

img

img

  • 写回答
  • 好问题 提建议
  • 追加酬金
  • 关注问题
  • 收藏
  • 邀请回答

2条回答 默认 最新

  • 封左 2021-08-07 08:12
    已采纳

    这是辗转相除法,也就是欧几里得算法求最大公约数的思路:
    两个正整数a和b(a>b),它们的最大公约数等于a除以b的余数c和b之间的最大公约数。比如10和25,25除以10商2余5,那么10和25的最大公约数,等同于10和5的最大公约数。
    先计算出a除以b的余数c,把问题转化成求出b和c的最大公约数;然后计算出b除以c的余数d,把问题转化成求出c和d的最大公约数;再然后计算出c除以d的余数e,把问题转化成求出d和e的最大公约数

    评论
    解决 1 无用
    打赏 举报
查看更多回答(1条)

相关推荐 更多相似问题