写点什么

辗转相除法求最大公约数(C 语言实现)

发布于: 2020 年 08 月 19 日

辗转相除法,一种求最大公约数的算法

已知:A / B = C ······ R  (A、B、C、R 皆是整数)

假设:D 是 A 的余数,D 也是 B 的余数,那么 D 就是 A 和 B 的公约数

D 是 A 和 B 的约数,则 A 和 B 是 D 的倍数,B * C 也是 D 的倍数

既然 A 与 B*C 都是 D 的倍数,那么 A 与 B*C 的也是 D 的倍数

A - B*C = R

所以 R 也是 D 的倍数

如果 D 是 A 或 B 的公约数,那么 D 也是 B 和 R 的公约数

故:(A,B)= (B,R)

由以上证明则可以求出最大的公约数

例如:求 72 和 28 的最大公约数

72 / 28 = 2 ······ 16

↓      ↓      ↓          ↓

28 / 16 = 1 ······ 12

↓      ↓      ↓          ↓

16 / 12 = 1 ······ 4

↓      ↓      ↓         ↓

12 / 4  =  3  ······ 0

现在可以知道 72 与 28 的最大公约数是 4

#include <stdio.h> int main(){    int a;                    // 除数    int b;                    // 被除数    int r=1;                 // 余数,赋初值为1     printf("输入除数与被除数(空格分开):");    scanf("%d %d",&a,&b);    while(r!=0){             // 如果a<b,亦无需颠倒ab,在计算中商0余除数本身,在下次运算中自可颠倒回来         r = a % b;        a = b;        b = r;    }    printf("最大公约数为:%d\n",a);        // 此时b的值已经在a中了,所以输出的a就是最大公约数     return 0;}
复制代码


用户头像

还未添加个人签名 2020.07.30 加入

还未添加个人简介

评论

发布
暂无评论
辗转相除法求最大公约数(C语言实现)