辗转相除法求最大公约数，计算过程说明和C语言实现_辗转相除法求最大公约数资源-CSDN文库

辗转相除法

最大公约数

需积分: 1 170 浏览量 2024-01-07 15:35:41 上传评论收藏 107KB PDF 举报

资源推荐

资源详情

资源评论

辗转相除法求最大公约数

辗转相除法又称欧几里得算法，是指用于计算两个非负整数 a，b 的最大公约

数。应用领域有数学和计算机两个方面。计算公式 gcd(a,b) = gcd(b,a mod b)。

两个整数的最大公约数是能够同时整除它们的最大的正整数。辗转相除法基于

如下原理：两个整数的最大公约数等于其中较小的数和两数相除余数的最大公

约数。所谓的辗转实际上指的是一个迭代运算的过程，迭代运算在编程语言里

的体现其实就是重复执行一段代码，在每一次执行过程中以上一次执行运算的

结果值为基础，运算出新值后代入下一次运算，不断用旧值推算新值，直至达

到终止条件为止。

辗转相除法过程的抽象描述如下：

初始化：两个整数之中的较大值 A 作为被除数，较小值 B 作为除数。

运算：对 A 和 B 进行取模（取余数）运算，得到余数 C。

迭代：将原本的除数 B 作为被除数，余数 C 作为除数，重复第 2 步的运算。

迭代终止：当某次运算中余数为 0 时，无法继续进行运算，算法结束，最后一

次运算的除数就是最初两个整数的最大公约数。

用 C 语言实现辗转相除算法：

// #include <math.h>

long int GCD(long int num1, long int num2) {

// 寻找两数最大公约数(欧几里得算法)

// 公式 GCD(被除数,除数)=GCD(除数,余数)

// 这里为了便于理解写的复杂了一些，新定义了三个局部变量

本内容试读结束，登录后可阅读更多

下载后可阅读完整内容，剩余2页未读，立即下载

内容反馈

shandongwill

粉丝: 3399
资源: 410

最新资源

资源上传下载、课程学习等过程中有任何疑问或建议，欢迎提出宝贵意见哦~我们会及时处理！点击此处反馈

feedback-tip