利用辗转相除法求两个自然数的最大公因数 程序如下:
[size=xx-large]
//利用辗转相除法求两个自然数的最大公因数
int gcd(int a, int b)
{
int r;
while(b)
{
r = a%b;
a = b;
b = r;
}
return a;
}
相关理论如下:
「辗转相除法」又叫做「欧几里得算法」,是公元前 300 年左右的希腊数学家欧几里得在他的著作《几何原本》提出的。利用这个方法,可以较快地求出两个自然数的最大公因数,即 HCF 或叫做 gcd。所谓最大公因数,是指几个数的共有的因数之中最大的一个,例如 8 和 12 的最大公因数是 4,记作 gcd(8,12)=4。
在介绍这个方法之前,先说明整除性的一些特点,注以下文的所有数都是正整数,以后不再重覆.
我们可以这样给出整除以的定义:
对於两个自然数 a 和 b,若存在正整数 q,使得 a=bq,则 b 能整除 a,记作 b | a,我们叫 b 是 a 的因数,而 a 是 b 的倍数。那麼如果 c | a,而且 c | b,则 c 是 a 和 b 的公因数。
由此,我们可以得出以下一些推论:
推论一:如果 a | b,若 k 是整数,则 a | kb。因为由 a | b 可知 ha=b,所以 (hk)a=kb,即 a | kb.
推论二:如果 a | b 以及 a | c,则 a | (b±c)。因为由 a | b 以及 a | c,可知 ha=b,ka=c,二式相加,得 (h+k)a=b+c,即 a | (b+c).同样把二式相减可得 a | (b-c)。
推论三:如果 a | b 以及 b | a,则 a=b。因为由 a | b 以及 b | a,可知 ha=b,a=kb,因此 a=k(ha),hk=1,由於 h 和 k 都是正整数,故 h=k=1,因此 a=b。
辗转相除法是用来计算两个数的最大公因数,在数值很大时尤其有用而且应用在电脑程式上也十分简单。其理论如下:
如果 q 和 r 是 m 除以 n 的商及余数,即 m=nq+r,则 gcd(m,n)=gcd(n,r)。 证明是这样的:
设 a=gcd(m,n),b=gcd(n,r)
则由 a | m 及 a | n,可得 a | (m-nq)(由推论一及推论二得出的),即 a | r ,又 a | n,所以 a | b。
由 b | r 及 b | n,可得 b | (nq+r),即 b | m,又 b | n,所以b | a。
因为 a | b 并且 b | a,所以 a=b,即 gcd(m,n)=gcd(n,r)。
举例计算 gcd(546, 429),由於 546=1(429)+117,429=3(117)+78,117=1(78)+39,78=2(39),因此
gcd(546, 429)
=gcd(429, 117)
=gcd(117, 78)
=gcd(78, 39)
=39
此处再添加一个程序例子,不过不是利用辗转相除法
求最大公约数和最小公倍数:
#include <iostream>
using namespace std;
int gec,lcm;
void process(int x,int y)
{
gcd=x<y?x:y;
lcm=x<y?y:x;
for(gcd=x<y?x:y;gcd>1;gcd--)if(x%gcd==0&&y%gcd==0)break;
for(lcm=x<y?x:y;lcm>1;lcm++)if(lcm%x==0&&lcm%y==0)break;
return;
}
[/size]
分享到:
相关推荐
编写一个方法,求两个自然数的最大公约数和最小公倍数 c#
用C#编程求两个自然数的最大公约数和最小公倍数
1. Java不同数据类型变量的使用 ①定义不同的字符变量,依次给这些变量赋值:’A’,’2’,’猫’,’b’并输出结果;...2. 计算最小公倍数和最大公约数 ①定义两个整型变量m,n; ②计算最大公约数; ③最小公倍数;
这是一个算法设计的题目,要求以三种方式实现最大公约数的求法,包括欧几里得法,循环测试法,质因数分解法。代码中可能没有整理好,还有一部分的质因数求法的算法。大家共同努力。
用辗转相除法求几个数的最大公约数,可以先求出其中任意两个数的最大公约数,再求这个最大公约数与第三个数的最大公约数,依次求下去,直到最后一个数为止。最后所得的那个最大公约数,就是所有这些数的最大公约数。
用连续整数检测法求两个整数的最大公约数a:if(m%t==0) {if(n%t!=0) {t--; goto a;} else printf("%d",t); } else {t--; goto a;}}
Description 给定任意两个正整数m和n,求出它们的最大公约数。 Input 两个正整数m和n Output m和n的最大公约数 Sample Input 6 9 Sample Output 3
最大公约数:如果有一个自然数a能被自然数b整除,则称a为b的倍数,b为a的约数。几个自然数公有的约数,叫做这几个自然数的公约数。公约数中最大的一个公约数,称为这几个自然数的最大公约数。
求两个自然数m和n的最大公约数。 分别使用三种算法实现: //连续整除算法 //欧几里得算法 //分解质因数算法 适用人群:算法入门或对算法很感兴趣的朋友,算是对算法有个初步的认识。 使用场景:本资源使用案例是...
求两个自然数m和n的最大公约数。 理解这样一个观点:不同的算法能够解决相同的问题,这些算法的解题思路不同,复杂程度不同,解题效率也不同。
给定两个自然数,求这两个数的最大公约数。 分析: 单看题目的话,非常简单,我们可以循环遍历自然数,如果能够整除两个自然数,就把这个数记下来,在这些记录中找到最大的一个。 但是这样做有几个缺点:一是做除...
用JAVA编写求自然数n到m的和,经过调试没有错误!
最大公约数:指两个或多个整数共有约束中最大的一个。 最小公倍数:如果有一个自然数a能被自然数b整除,则称a为b的倍数,b为a的约数,对于两个整数来说,指该两数共有倍数中最小的一个。 代码如下:/// <summary>///...
java代码-例子3-6 求前20个自然数的积。
c++ 实现一个自然数表示成几个自然数的和,输出所有自然数和的表示方式
一个数的所有约数的MATLAP代码。约数定义:约数,又称因数。整数a除以整数b(b≠0) 除得的商正好是整数而没有余数,我们就说a能被b整除,或b能整除a。a称为b的倍数,b称为a的...同时,它可以在特定情况下成为公约数。
C语言程序设计-求一个n位自然数的各位数字的积;(n 是小于10的自然数).c
第一行是两个整数n和x,n表示自然数的个数,x表示要查找的自然数,两者之间用空格隔开; 第2至n+1每行一个自然数。 Output 对应每组输入,如果查找到x,则每行输出两个整数,分别是自然数和该数出现的次数,其间...
递归求前25个自然数的和.cpp