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

这篇具有很好参考价值的文章主要介绍了辗转相除法——求最大公约数(易懂详解)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

定义

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

辗转相除法:欧几里得算法又称辗转相除法,是指用于计算两个非负整数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。文章来源地址https://www.toymoban.com/news/detail-566732.html

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运行

辗转相除法,算法,c语言

到了这里,关于辗转相除法——求最大公约数(易懂详解)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 算法--辗转相除法

    遇到一题算法题,如下: 求字符串的最大公因子? 对于字符串 s 和 t,只有在 s = t + … + t(t 自身连接 1 次或多次)时,我们才认定 “t 能除尽 s”。 给定两个字符串 str1 和 str2 。返回 最长字符串 x,要求满足 x 能除尽 str1 且 x 能除尽 str2 。 约数。整数a除以整数b(b≠0)除得

    2024年02月13日
    浏览(52)
  • C语言辗转相除法运用 24/1/22笔记错题整理

    题目: 思路:一开始用最普通的方法去解题,计算量较大,但是 求最大公约数常用的有两种简单方法,一是九章算术中的 更相减损术 :大数减小数直到相等,相等的数即最大公约数,该算法 时间复杂度约为O(N) ;二是欧几里得的 辗转相除法 :大数除以小数取余数(相当于模

    2024年01月23日
    浏览(56)
  • 算法通关村十三关 | 辗转相除法、素数和丑数

            辗转相除法又称欧几里得算法,求两个数的最大公因数,希腊数学家喜欢用图形来处理问题,于是 将要求最大公约数问题转化为,以两个数字构成矩形,寻找可以铺满整个矩形的最大正方形的边长问题。 例如8和12的最大公因数是4,记作gcd(8,12)=4,辗转相除法的规则

    2024年02月09日
    浏览(47)
  • C语言的三个经典题目:三步翻转法、杨氏矩阵、辗转相除法

    三步翻转法是C语言中用来求旋转字符串的一种进阶方法,我们以具体例题对其进行介绍。 例:求一个字符串左旋n个字符后得到的新字符串 普通方法实现 我们知道,左旋一个字符一共分为三步: 将字符串的第一个字符存放到临时变量中; 将字符串中除’\\0’外的所有字符整

    2024年02月02日
    浏览(50)
  • 快乐地谈谈:关于RSA算法中求私钥d的欧几里得方法(辗转相除法)考试向的欸

    关于RSA算法本身,就提及一下,它是属于非对称密码体制. 基本的加密方式就如下图所示: c为加密后的密文,m为加密前的明文 其中一般会给出公开密钥n、e的值,这样根据规则,便可以实现加密过程。而题目往往需要进行解密,那么就需要 先求解出p、q,随后再求解出私钥

    2024年02月04日
    浏览(38)
  • 【约数】求最大公约数——递归

    请使用递归算法计算正整数n和m的最大公约数GCD(n,m)。 G C D ( n , m ) = { = m , 当 m = n 且 n m o d m = 0 = G C D ( m , n ) , 当 n m 时 = G C D ( m , n m o d    m ) , 其他 GCD(n,m)=left{begin{matrix} =m,当 m=n 且 n mod m =0\\\\ =GCD(m,n),当nm时\\\\ =GCD(m,n mod m),其他 end{matrix}right. GC D ( n , m ) = ⎩ ⎨ ⎧ ​ = m

    2024年02月03日
    浏览(43)
  • 最大公约数和最小公倍数问题

    等差数列 蓝桥杯192 gcd问题 题目描述 数学老师给小明出了一道等差数列求和的题目。但是粗心的小明忘记了一 部分的数列,只记得其中 N 个整数。 现在给出这 N 个整数,小明想知道包含这 N 个整数的最短的等差数列有几项? 思路:求出每一项之差的最大公约数,以这个

    2023年04月09日
    浏览(41)
  • 最大公约数的四种方法

    求两数的最大公约数,一共有四种方法:暴力穷举法、更相减损法、辗转相除法、stein 算法,小女不才,花了几天的时间终于把这几种方法全部弄明白,现在就把它们全部分享出来。 首先,假设被求的两个数为 x、y,且 x y。最大公约数 d = gcd (x , y) 正如名字所说,暴击穷举法

    2024年02月05日
    浏览(73)
  • C++ 最大公约数与最小公倍数

    (一)简单的两个正整数  求 最大公约数 (引入专题) 思路: 根据 “欧几里得算法”  ,即 “辗转相除法” 原理如下: 题意: 求出   a  , b  两个正整数的最大公约数 设  k = a / b,   r = a % b 即    a = k * b + r 又设  d  为 a 和 b 的一个公约数 那么由  r = a - k * b,  可

    2024年02月06日
    浏览(48)
  • 辗转相除为什么能得到最大公因式?高等代数1.2

    我们来继续探索两个多项式之间的关系,今天的研究对象是最大公因式。 一)最大公因式 因式 :g(x)|f(x),则f(x)=h(x)*g(x),g(x)是f(x)的 因式。 倍式:f(x)是g(x)的倍式。 最大公因式的定义如下图。 最大公因式从字面上就可以理解了,一是公因式,二是要最大的那一些,至于为什么

    2024年02月06日
    浏览(60)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包