【C语言-辗转相除法】代码学习

辗转相除法

• C语言求最大公约数最小公倍数例题
• 辗转相除法
• 辗转相除法原理
• 参照习题
• 不错的csdn博客

C语言求最大公约数最小公倍数例题

例：使用while循环求两个正整数的最大公约数和最小公倍数。

#include 

int main(int argc, char** argv)
{
    int a, b, c, m, t;
    printf("请输入两个数：");
    scanf("%d,%d", &a, &b);
    if (a < b)
    {
        t = a;
        a = b;
        b = t;
    }
    m = a * b;
    c = a % b;
    while (c != 0)
    {
        a = b;
        b = c;
        c = a % b;
    }

    printf("最大公约数是：%d\n", b);
    printf("最小公倍数是：%d\n", m / b);
}

---

辗转相除法

假设我们要求出161和63的最大公约数，辗转相除法步骤如下：
161/63=2···35(161%63)
63/35=1···28(63%35)
35/28=1···7(35%28)
28/7=4···0
所以最大公约数为 7

---

辗转相除法原理

设两个正整数 a 和 b ，要求是求这两个数的最大公约数。
假设最大公约数为 m；那么我们可知 a 可以整除 m ，b 也可以整除 m，(a-b) 也可以整除 m ，且 a-2b 也可以整除 m（a-2b>0），以此类推，a-nb 也可以整除 m（a-nb>0，且a-nb

---

参照习题

csdn: while循环：最大公约数和最小公倍数

---

不错的csdn博客

csdn(哈哈哈哈嘻哈从) 辗转相除法的原理