最新消息: USBMI致力于为网友们分享Windows、安卓、IOS等主流手机系统相关的资讯以及评测、同时提供相关教程、应用、软件下载等服务。

辗转相除法——求最大公约数(易懂详解)

互联网 admin 4浏览 0评论

辗转相除法——求最大公约数(易懂详解)

定义

最大公因数:也称最大公约数、最大公因子,指两个或多个整数共有约数中最大的一个。

辗转相除法:欧几里得算法又称辗转相除法,是指用于计算两个非负整数a,b的最大公约数。应用领域有数学和计算机两个方面。计算公式gcd(a,b) = gcd(b,a mod b)。

举例理解

比如现在要求这两个数 32,26的最大公约数,解法如下:

32/26=1...6  (此行除数26作下一行的被除数,余数作为除数)

26/6=4...2  (此行同理)

6/2=3...0  (此处余数为零,意味着最大公约数就是2)

反复把一个式子中的除数当作被除数去除余数,直到最后余数等于0。

最大公约数就是最后那个式子的除数,本例就是2。

C语言代码

#include <stdio.h>
int main()
{int u, v;scanf("%d %d", &u, &v);while (v != 0){int tmp = u % v;u = v;v = tmp;}printf("%d", u);return 0;}

Visual Studio 2022运行

辗转相除法——求最大公约数(易懂详解)

定义

最大公因数:也称最大公约数、最大公因子,指两个或多个整数共有约数中最大的一个。

辗转相除法:欧几里得算法又称辗转相除法,是指用于计算两个非负整数a,b的最大公约数。应用领域有数学和计算机两个方面。计算公式gcd(a,b) = gcd(b,a mod b)。

举例理解

比如现在要求这两个数 32,26的最大公约数,解法如下:

32/26=1...6  (此行除数26作下一行的被除数,余数作为除数)

26/6=4...2  (此行同理)

6/2=3...0  (此处余数为零,意味着最大公约数就是2)

反复把一个式子中的除数当作被除数去除余数,直到最后余数等于0。

最大公约数就是最后那个式子的除数,本例就是2。

C语言代码

#include <stdio.h>
int main()
{int u, v;scanf("%d %d", &u, &v);while (v != 0){int tmp = u % v;u = v;v = tmp;}printf("%d", u);return 0;}

Visual Studio 2022运行

发布评论

评论列表 (0)

  1. 暂无评论