gcd算法:给定俩个正整数m,n(m>=n),求它们的最大公约数。(注意,一般要求m>=n,若m<n,则要先交换m<->n。下文,会具体解释)。以下,是此算法的具体流程:
1、[求余数],令r=m%n,r为n除m所得余数(0<=r<n);
2、[余数为0?],若r=0,算法结束,此刻,n即为所求答案,否则,继续,转到3;
3、[重置],置m<-n,n<-r,返回步骤1.
此算法的证明,可参考计算机程序设计艺术第一卷:基本算法。
ok,下面,举一个例子,你可能看的更明朗点。
比如,给定m=544,n=119,
则余数r=m%n=544%119=68; 因r!=0,所以跳过上述步骤2,执行步骤3。;
置m<-119,n<-68,=>r=m%n=119%68=51;
置m<-68,n<-51,=>r=m%n=68%51=17;
置m<-51,n<-17,=>r=m%n=51%17=0,算法结束,
此时的n=17,即为m=544,n=119所求的俩个数的最大公约数。
再解释下上述gcd(m,n)算法开头处的,要求m>=n 的原因:举这样一个例子,如m<n,即m=119,n=544的话,那么r=m%n=119%544=119,
因为r!=0,所以执行上述步骤3,注意,看清楚了:m<-544,n<-119。看到了没,尽管刚开始给的m<n,但最终执行gcd算法时,还是会把m,n的值交换过来,以保证m>=n。
/**
* 求最大公约数
*
* @param m
* @param n
* @return
*/
public static int gcd(int m, int n)
{
if (m < 0 || n < 0)
{
System.err.println("ERROR!!");
return -1;
}
while (true)
{
if ((m = m % n) == 0)
return n;
if ((n = n % m) == 0)
return m;
}
}
分享到:
相关推荐
python求最大公约数和最小公倍数 #辗转相除法 def gcd(a,b): #最大公约数函数,且最小公倍数 = 两个数相乘 / 最大公约数 if b == 0: return a else: return gcd(b,a%b) print("请输入两个数:") j,k = input()....
基于VHDL语言求最大公约数的GCD算法ISE软件实现,用spanten 3E的fpga开发板实现
三种方法求最大公约数
该程序使用二进制 gcd 算法找到最大公约数,如 Menezes、van Oorschot 和 Vanstone 的《应用密码学手册》中所述。
求两个数最大公约数,利用欧几里德算法,辗转相除法。详细内容看资料,留作备份。
三种求最大公约数的算法。用c语言编写的。
本文实例讲述了Python基于递归和非递归算法求两个数最大公约数、最小公倍数。分享给大家供大家参考,具体如下: 最大公约数和最小公倍数的概念大家都很熟悉了,在这里就不多说了,今天这个是因为做题的时候遇到了...
Stein 算法或二进制 GCD 算法是计算两个非负整数的最大公约数的算法。 Stein 的算法用算术移位、比较和减法代替除法。Stein算法是一种计算两个数最大公约数的算法,是针对欧几里德算法在对大整数进行运算时,需要试...
输入为两个32位数值,用辗转相减法实现的最大公约数算法进行输出,含有置位信号。
c语言编写的求解最大公约数的算法,非常简单,只有几行代码
包含两个算法,一个为辗转相除法,一个为连续整数检测法。而且算法中加入计数法对比两种算法的时间复杂度。
GCD 使用计算最大公约数。 例子 var gcd = require ( 'gcd' ) ; var n = gcd ( 121 , 44 ) ; console .... 使用欧几里德算法返回整数a和b最大公约数。 安装 用做: npm install gcd 执照 麻省理工学院
求解最大公约数和最小公倍数的方法有很多种,如质因数分解法、短除法、辗转相除法(欧几里得算法)等。 在实际应用中,这两个概念广泛应用于数学各个分支以及日常生活中,如分数化简、时间与速度问题、工程设计等...
今天整理了一下用递归法求最大公约数(gcd)和最小公倍数(lcm)。主要的工作是求最大公约数。数学上可以用辗转法求最大公约数
最大公因数使用辗转相除法来求,最小公倍数则由这个公式来求: GCD * LCM = 两数乘积
java求最大公约数 要在Java中求两个整数的最大公约数(GCD),你可以使用欧几里得算法,也称为辗转相除法。这个算法的基本思想是反复用较小的数去除较大的数,直到余数为零为止。最后一个余数就是最大公约数。
求解多个数的最大公约数,其中in.txt放入要计算的n个数,并将n也放在最前方,随后,存放这n个整数,最后结果放在out.txt中。
title: Maximum GCD(最大公约数)categories: [算法题解]传送门:UVA 11827 - Maximum GCD题目大意:给你几组数
在C#中,计算两个整数的最大公约数(Greatest Common Divisor, GCD)可以通过多种算法实现,其中最著名和高效的是欧几里得算法。欧几里得算法基于这样一个事实:两个整数的最大公约数等于其中较小的数和两数的差的...
GCD 使用欧几里得算法计算两个整数 m 和 n 的最大公约数。 欧几里德算法指出 m 和 n 的 gcd 与 n 和 mod(m,n) 的 gcd 相同。