
- 基本概念
- 多个整数共有约数中最大的一个
- 相对应概念
- 最小公倍数
- 别 名
- Highest Common Factor(HCF)
- 中文名
- 最大公约数
- 所属学科
- 数学
- 外文名
- Greatest Common Divisor(GCD)
-
2020-11-24 09:11:20
Python程序查找最大公因数(HCF)或最大公约数(GCD)
在此示例中,您将学习使用两种不同的方法查找两个数字的GCD:函数和循环以及欧几里得算法
要理解此示例,您应该了解以下Python编程主题:
两个数的最大公因数(H.C.F)或最大公约数(G.C.D)是能完美地将两个给定数相除的最大正整数。例如,H.C.F(12, 14)等于2。
源代码:使用循环
示例# Python程序查找两个数字的H.C.F
# 定义一个函数
def compute_hcf(x, y):
# 选择较小的数字
if x > y:
smaller = y
else:
smaller = x
for i in range(1, smaller+1):
if((x % i == 0) and (y % i == 0)):
hcf = i
return hcf
num1 = 54
num2 = 24
print("H.C.F. 是", compute_hcf(num1, num2))
输出结果H.C.F. 是 6
这里,存储在变量num1和num2中的两个整数被传递给compute hcf()函数。该函数计算H.C.F.这两个数字并返回它。
在这个函数中,我们首先确定两个数字中较小的那个F只能小于或等于最小的数。然后我们使用一个for循环从1到那个数字。
在每次迭代中,我们检查我们的数字是否完美地将两个输入数字相除。如果是这样,我们将这个数字存储为H.C.F.,在循环结束时,我们得到的最大的数字完美地将两个数字相除。
上述方法易于理解和实施,但是效率不高。查找HCF的一种更有效的方法是欧几里得算法。
欧几里得算法
该算法基于以下事实:两个数字的HCF也将它们的差除。
在此算法中,我们将较大者除以较小者,然后取余数。现在,将较小者除以该余数。重复直到剩余为0。
例如,如果我们想求54和24的hcf,我们用54除以24。余数是6。24除以6,余数是0。因此,6是必需的hcf
源代码:使用欧几里得算法
示例# 函数查找HCF的使用欧几里德算法
def compute_hcf(x, y):
while(y):
x, y = y, x % y
return x
hcf = compute_hcf(300, 400)
print("The HCF is", hcf)
在这里我们循环直到y变为零。该语句x, y = y, x % y在Python中交换值。单击此处以了解有关在Python中交换变量的更多信息。
在每次迭代中,我们同时将y的值放在x中,其余的(x % y)放在y中。当y变为0时,我们得到x的hcf。
更多相关内容 -
Python实现利用最大公约数求三个正整数的最小公倍数示例
2021-01-01 13:23:50本文实例讲述了Python实现利用最大公约数求三个正整数的最小公倍数。分享给大家供大家参考,具体如下: 在求解两个数的小公倍数的方法时,假设两个正整数分别为a、b的最小公倍数为d,最大公约数为c。存在这样的关系d... -
Python基于辗转相除法求解最大公约数的方法示例
2020-12-23 16:48:24本文实例讲述了Python基于辗转相除法求解最大公约数的方法。分享给大家供大家参考,具体如下: 之前总结过一次高德纳TAOCP中的最大公约数求解,其实课后题中的算法修改要求实现的是辗转相除法求解最大公约数。 这个... -
Python基于递归算法求最小公倍数和最大公约数示例
2020-09-20 05:14:35主要介绍了Python基于递归算法求最小公倍数和最大公约数,结合实例形式分析了Python使用递归算法进行数值计算的相关操作技巧,需要的朋友可以参考下 -
python求最大公约数和最小公倍数的简单方法
2021-01-20 01:55:57python怎么求最大公约数和最小公倍数 一、求最大公约数 用辗转相除法求最大公约数的算法如下: 两个正整数a和b(a>b),它们的最大公约数等于a除以b的余数c和b之间的最大公约数。比如10和25,25除以10商2余5,那么10... -
详解C语言求两个数的最大公约数及最小公倍数的方法
2021-01-21 18:05:39求两个正整数的最大公约数 思路:这是一个很基本的问题,最常见的就是两种方法,辗转相除法和辗转相减法。通式分别为 f(x, y) = f(y, x%y), f(x, y) = f(y, x – y) (x >=y > 0)。根据通式写出算法不难,这里就... -
Python自定义函数实现求两个数最大公约数、最小公倍数示例
2020-09-20 11:51:56主要介绍了Python自定义函数实现求两个数最大公约数、最小公倍数,结合实例形式分析了Python求解两个数最大公约数与最小公倍数相关原理与算法实现技巧,需要的朋友可以参考下 -
PTA-公因数与公约数
2021-01-03 14:11:34最大公因数(Greatest Common Divisor,简称GCD),也称最大公约数、最大公因子,指两个或多个整数共有约数中最大的一个。整数m和n的最大公约数记为GCD(m, n)。 最小公倍数(Least Common Multiple,简称LCM)是指两个... -
C++ 实现求最大公约数和最小公倍数
2020-12-26 08:06:24C++ 实现求最大公约数和最小公倍数 最大公约数 辗转相除法: int maxDivisor(int a, int b) { int c = b; while (a%b != 0) { c = a%b; a = b; b = c; } return c; } 辗转相减法: int maxDivisor(int a,... -
求最大公约数 最大公因数 语言实现输出一个整数的最大公约数(因数),四种算法实现
2022-04-23 12:15:36求最大公约数 c语言实现输出一个整数的最大公约数(因数),四种算法实现算法设计:
方法一:
第一种思路是枚举(穷举法、列举法),但是枚举又可以分为两种方法。第一种,采用穷举法按从小到大(初值为1,最大值为两个整数当中较小的数)的顺序将所有满足条件的公约数列出,输出其中最大的一个;第二种,按照从大(两个整数中较小的数)到小(到最小的整数1)的顺序求出第一个能同时整除两个整数的自然数,即为所求。
代码示例如下:
#include <stdio.h> int main() { int a, b; scanf("%d %d", &a, &b);//低版本编译器使用scanf 高版本编译器使用scanf_s int i; int gcd; gcd = 1; for(i = (a<b?a: b); i > 0; i--) { if(a % i == 0 && b % i == 0) { gcd = i; break; } } printf("gcd = %d\n", gcd); return 0; }
#include <stdio.h> int Get_Max_Comm_Divisor(int num1, int num2) { int i = 0; //获取两个整数的最小值 int min = num1 < num2 ? num1 : num2; //从两个数的最小值开始递减遍历 for (i = min; i > 0; i--) { //i为num1和num2的公倍数 if (num1 % i == 0 && num2 % i == 0) break; } return i; } int main() { int num1 = 0, num2 = 0; puts("请输入两个正整数."); scanf_s("%d%d", &num1, &num2); printf("最大公约数为%d.\n", Get_Max_Comm_Divisor(num1, num2)); return 0; }
运行结果如下:
方法二:
辗转相除法
1.如果b == 0,计算结束,a为最大公约数;
2.否则,计算a除以b的余数,让a等于b,而b等于那个余数;
3.返回第1步
代码示例如下:
#include <stdio.h> int main(int argc, const char* argv[]) { int a; int b; int temp; scanf_s("%d %d", &a, &b);//低版本编译器使用scanf 高版本编译器使用scanf_s while (b != 0) { temp = a % b; a = b; b = temp; } printf("gcd = %d\n", a); return 0; }
代码运行结果如下:
方法三:
更相减损法
1.求出两个正整数num1和num2的差值diff;
2.将num2赋值给num1,让上次相减时的减数num2作为下次相减时的被减数。
同时将当前的差值diff作为下次相减的减数。
这样一直地辗转相减,直到差值为0,这时的除数num2就是我们要求的最大公因数
代码示例如下:
#include <stdio.h> int Get_Max_Comm_Divisor(int num1, int num2) { //两数相减的结果(取正值) int diff = num1 > num2 ? num1 - num2 : num2 - num1; while (diff != 0) { num1 = num2; //更新被减数 num2 = diff; //更新减数 diff = num1 > num2 ? num1 - num2\ : num2 - num1; //更新两数相减的结果(取正值) } return num2; //最后的减数即为最大公因数 } int main() { int num1 = 0, num2 = 0; puts("请输入两个正整数."); scanf_s("%d%d", &num1, &num2);//低版本编译器用scanf 高版本编译器用scanf_s printf("最大公约数为%d.\n", Get_Max_Comm_Divisor(num1, num2)); return 0; }
代码运行结果如下:
方法四:
Stein算法函数递归调用
#include "stdio.h" #include <windows.h> int gcd(int u, int v) { if (u == 0) return v; if (v == 0) return u; if (~u & 1) { if (v & 1) return gcd(u >> 1, v); else return gcd(u >> 1, v >> 1) << 1; } if (~v & 1) return gcd(u, v >> 1); if (u > v) return gcd((u - v) >> 1, v); return gcd((v - u) >> 1, u); } int main() { int z[2][20] = { {1,1},{31,43,46,65,43,58,55,54,55,56,98,78,96,54,78,85,57,12,36,15} }; int i = 0; double run_time; LARGE_INTEGER time_start; //开始时间 LARGE_INTEGER time_over; //结束时间 double dqFreq; //计时器频率 LARGE_INTEGER f; //计时器频率 int m, n, t2; getch(); QueryPerformanceFrequency(&f); dqFreq = (double)f.QuadPart; QueryPerformanceCounter(&time_start); //计时开始 for (i = 0; i < 20; i++) { t2 = gcd(z[0][i], z[1][i]); printf("The higest common divisor is %d\n", t2); } QueryPerformanceCounter(&time_over); //计时结束 run_time = 1000000 * (time_over.QuadPart - time_start.QuadPart) / dqFreq; //乘以1000000把单位由秒化为微秒,精度为1000 000/(cpu主频)微秒 printf("\nrun_time:%fus\n", run_time); return 0; }
Stein算法非函数递归调用
#include "stdio.h" #include <windows.h> int Stein(int x,int y) /*return the greatest common divisor of x and y*/ { int factor=0; int temp; if(x<y) { temp=x; x=y; y=temp; } if(0==y) { return 0; } while(x!=y) { if(x&0x1) { if(y&0x1) { y=(x-y)>>1; x-=y; } else { y>>=1; } } else { if(y&0x1) { x>>=1; if(x<y) { temp=x; x=y; y=temp; } } else { x>>=1; y>>=1; ++factor; } } } return (x<<factor); } int main() { int z[2][20] = {{1,1},{31,43,46,65,43,58,55,54,55,56,98,78,96,54,78,85,57,12,36,15}}; int i = 0; double run_time; LARGE_INTEGER time_start; LARGE_INTEGER time_over; double dqFreq; LARGE_INTEGER f; int m,n,t2; getch(); QueryPerformanceFrequency(&f); dqFreq=(double)f.QuadPart; QueryPerformanceCounter(&time_start); for( i = 0; i < 20; i++){ t2 = Stein(z[0][i],z[1][i]); printf("The higest common divisor is %d\n",t2); } QueryPerformanceCounter(&time_over); run_time=1000000*(time_over.QuadPart-time_start.QuadPart)/dqFreq; printf("\nrun_time:%fus\n",run_time); return 0; }
代码运行效果如下:
编者注:以上对本小题的代码编写的多种方法,欢迎大家收藏借鉴并转发;
以上代码仅供参考,如有问题欢迎大家在留言区批评指正;
版权所有,翻印必究,如有雷同纯属巧合,转载请注明出处。
By CRH380AJ2808 2022.04.23
————————————————
版权声明:本文为CSDN博主「CRH380AJ2808」的原创文章,遵循CC 4.0 BY-SA版权协议,转载请附上原文出处链接及本声明。
原文链接:https://blog.csdn.net/JH13thpig/article/details/124361837 -
C++求四个正整数最大公约数的方法
2020-12-26 01:42:48本文实例讲述了C++求四个正整数最大公约数的方法。分享给大家供大家参考,具体如下: /* * 作 者: 刘同宾 * 完成日期:2012 年 11 月 16 日 * 版 本 号:v1.0 * * 输入描述: 输入四个正整数,输出其最大公约数。 ... -
gcd函数(最大公约数)(最大公因数)
2021-08-29 22:48:05最大公因数(英语:highest common factor,hcf)也称最大公约数(英语:greatest common divisor,gcd)是数学词汇,指能够整除多个整数的最大正整数。而多个整数不能都为零。例如8和12的最大公因数为4。 求两个...gcd函数即为实现求两数最大公约数(最大公因数)的函数
求两个整数最大公约数主要的方法:
1.穷举法:分别列出两整数的所有约数,并找出最大的公约数。
2.素因数分解:分别列出两数的素因数分解式,并计算共同项的乘积。
3.短除法:两数除以其共同素因数,直到两数互素时,所有除数的乘积即为最大公约数。
4.辗转相除法:两数相除,取余数重复进行相除,直到余数为0时,前一个除数即为最大公约数。gcd函数的一些实现方法:
库函数也有已经实现的gcd函数:
int k=__gcd(n,m);
#include <iostream> #include <algorithm> using namespace std; int a,b; int main() { cin>>a>>b; cout<<__gcd(a,b)<<endl; return 0; }
int、long long类型都可以,需要注意的是两个类型必须要相同,还有就是不能用浮点型,它头文件是algorithm。
-
递归法求最大公约数和最小公倍数的实现代码
2021-01-01 02:02:07当r == 0时,即num1可以被num2整除,显然num2就是这两个数的最大公约数。 当r != 0时,令num1 = num2(除数变被除数),num2 = r(余数变除数),再做 r = num1 % num2。递归,直到r == 0。 以上数学原理可以用... -
使用Python求解最大公约数的实现方法
2020-12-23 18:22:31欧几里德算法又称辗转相除法, 用于计算两个整数a, b的最大公约数。其计算原理依赖于下面的定理: 定理: gcd(a, b) = gcd(b, a mod b) 证明: a可以表示成a = kb + r, 则r = a mod b 假设d是a, b的一个公约数,... -
c++求最大公约数
2014-12-27 21:26:00有关c++求最大公约数的代码,用的是辗转相除法,很简单的算法过程,主要是求最大公约数 -
用python编写两个正整数的最大公约数和最小公倍数的小程序
2020-12-22 11:47:41show 程序代码 废话不多说,直接上程序片段 nummax,nummin=eval(input("请输入两个正整数,并用逗号连接:")...print("其中最大公约数是:"+str(m)) print(str(nummax)+"和"+str(nummin)+"的最小公倍数数是: -
python如何求解两数的最大公约数
2020-12-25 15:01:27给定两个自然数,求这两个数的最大公约数。 分析: 单看题目的话,非常简单,我们可以循环遍历自然数,如果能够整除两个自然数,就把这个数记下来,在这些记录中找到最大的一个。 但是这样做有几个缺点:一是做除... -
Python基于递归和非递归算法求两个数最大公约数、最小公倍数示例
2020-12-24 19:21:23本文实例讲述了Python基于递归和非递归算法求两个数最大公约数、最小公倍数。分享给大家供大家参考,具体如下: 最大公约数和最小公倍数的概念大家都很熟悉了,在这里就不多说了,今天这个是因为做题的时候遇到了... -
php计算两个整数的最大公约数常用算法小结
2020-12-18 14:18:31本文实例讲述了php计算两个整数的最大公约数常用算法。分享给大家供大家参考。具体如下: 复制代码 代码如下:<?php //计时,返回秒 function microtime_float () { list( $usec , $sec ) = explode ( ” ” ... -
欧几里德算法求最大公约数——C++代码
2020-06-08 17:50:50课程的随堂作业,C语言的,用dev就能运行,萌新代码,勿喷,仅仅帮助不想写作业的朋友方便一下,反正老师也不会仔细检查的 -
求两个数的最大公约数和最小公倍数
2016-10-07 22:05:28用java写的小程序,输入两个数,求得他们的最大公约数和最小公倍数 -
算法_用欧几里得算法求最大公因数_
2021-09-29 01:52:41用扩展欧几里得算法求任意两个数字的最大公因数 -
用计算机计算最大公因数,利用计算器求两个较大数的最大公约数的简便方法
2021-06-23 03:56:55垒三塑圭ke.xuejiaoyujia 数学教育研究利用计算器求两个较大数的最大公约数的简便方法胡苏琦(中山一中广东中山528400)在高一数学必修A3课本中这一章介绍了如何求两个较大的数的最大公约数的方法——辗转相除法,...!塑!垒三塑圭
ke.xuejiaoyujia 数学教育研究
利用计算器求两个较大数的最大公约数的简便方法
胡苏琦
(中山一中广东中山528400)
在高一数学必修A3课本中这一章介绍了如何求两
个较大的数的最大公约数的方法——辗转相除法,这种方法能
较快求出两个较大的数的最大公约数,但原理难理解,步骤复
杂。现在是信息技术的时代,有没有能够利用信息技术简便求
出两个较大的数的最大公约数?笔者发现是有的,且原理简单。
定理1:若詈=寺(其中p-,q互质)则m,n的最大公约数
为里或旦
P q
证明:·.·旦=卫
“ q
.‘.m2pk.n2qk
又p、q互质
k=旦是m、rt的最大公因数(即最大公约数)
P
同理可得k=三握m、n的最大公因数(即最大公约数)
q
用辗转相除法可以求出两个自然数的最大公因数
825l=6105x1+2146
6105=2146 X2+1813
2146=1813 Xl+333
18】3=333 X5+148
333:148×2+37
148=37 x4
则根据定理4。148与37的最大公约数就是8251与6105
的最大公约数,故8251与6105的最大公约数是37。这过程不
断交换除数被除数,容易混淆,过程也复杂。根据定理l利用计
算器我们能够更快求出两个较大的数的最大公约数。
第一步:输入m÷n,结果为x
第二步:按“shift”+“d/c”,就能将x转化假分数形式卫
q
第三步:输入m÷P=,这样通过计算器三步就能得到m、n
的最大公因数k
我们以上面求8251。6105的最大公约数为例
第一步:输入8251÷6105,结果为1.351515152
第二步:按“shift”+“d/c”,就能将1.351515152转化假分
’11
数形式筹
1QJ
第三步:输入8215÷223。得到m、n的最大公因数37。结果
与用辗转相除法相同,步骤却省了很多。
练习验证:
‘
求下列两数最大公约数
(i)225,135②粥,196 劬2,168 ④153,119
并非求函数的定义域,教学时不需加大此部分难度.4作业布置
巩固练习:(教材%练习2).(个体练习为主,可让学生上4.1必做题:教材P7.习题2.2(A组)第7、8题.
迸台在黑板解题,强调格式)4.2选做题:教材%习题2.2(B组)第4题.
例2.(教材%例8)(讨论分析:比大小的依据?一师生共 4.3拓展题(选做):
练一小结:利用单调性比大小)4.3.1已知函数Y=f(2‘)的定义域为[一1,1],则函数Y
解: =f(1092x)的定义域为——
(1)解法1:用图形计算器或多媒体画出对数函数Y=l092x 4.3.2求函数Y=2+l092x(x≥1)的值域.
的图象.在图象上,横坐标为3.4的点在横坐标为8.5的点的4.3.3已知log.
r月三一⋯ . .4.3.4已知0l,ab>1.比较IogI÷,Iog.109b
所以,10923.4
解法2:由函数Y+l092x在R+上是单调增函数,且3.4<
8.5,所以I0923.4
3归纳小结。强化思想
本节课的目的要求是掌握对数函数的概念、图象和性质.在
理解对数函数的定义的基础上,掌握对数函数的图象和性质是
本节课的重点.
①提问学生本节课学会了什么知识;
②总结本节课主要学习内容:
·212·
÷的大,J、o
(设计意图)作业按循序渐进的原则布置,既巩固本节课所
学知识。又培养自觉学习的习惯,在解题
-
PHP编程求最大公约数与最小公倍数的方法示例
2020-10-19 18:57:07主要介绍了PHP编程求最大公约数与最小公倍数的方法,涉及php数学计算的相关运算技巧,需要的朋友可以参考下 -
C#获取两个数的最大公约数和最小公倍数示例
2020-12-31 15:03:38最大公约数:指两个或多个整数共有约束中最大的一个。 最小公倍数:如果有一个自然数a能被自然数b整除,则称a为b的倍数,b为a的约数,对于两个整数来说,指该两数共有倍数中最小的一个。 代码如下:/// <summary>///... -
Python基于更相减损术实现求解最大公约数的方法
2020-09-20 16:02:44主要介绍了Python基于更相减损术实现求解最大公约数的方法,简单说明了更相减损术的概念、原理并结合Python实例形式分析了基于更相减损术实现求解最大公约数的相关操作技巧与注意事项,需要的朋友可以参考下