高一Python入门第四讲 最大公约数

高一Python入门第四讲 最大公约数

专栏推荐

高一Python入门第一讲：播下一颗种子.
高一python入门第二讲 知人亦知面.
高一Python入门第三讲 石头剪刀布.

联系

4.1 什么是最大公因数

最大公因数，也称最大公约数、最大公因子，指两个或多个整数共有约数中最大的一个。a，b的最大公约数记为（a，b），同样的，a，b，c的最大公约数记为（a，b，c），多个整数的最大公约数也有同样的记号。求最大公约数有多种方法，常见的有质因数分解法、短除法、辗转相除法、更相减损法。与最大公约数相对应的概念是最小公倍数，a，b的最小公倍数记为[a，b]。——“百度百科”

建构

4.2如何求最大公因数

4.2.1 列举法求最大公因数

述： 入两个大整数m,n, 输出m,n 的最大公因数。
输入样例： 12345678 的87654321
9876543211234567
输出样例： 1222222221

[参考代码]

 l.py
lmport tlme
m = lnt(lnput("m=•))
n = lnt(lnput("n="))
ifm <n: # 保证m > =
tl = time.time()
for in range(l,n•l):
if m ％ = = 0 and n ％ 一= 0
t2 = time.time()
print 「最大公约数％ d ， 用时‰ 2f 纩％ （ g 醚。t2 ． tl 〕）

4.2.2 更相减埙法求最大公约数

《九章算术》是中国古代的数学专著， 其中的更相减损术可以用来求两个数的最大公约数

原文是：可半者半之， 不可半者， 副置分母、子之数， 以少减多， 更相减损， 求其等也。以等壹数约之。
白话文译文：（ 如果需要对分数进行约分， 那么） 可以折半的话， 就折半（ 也就是用2 来约分） 。如果不可以折半的话， 那么就比较分母和分子的大小， 用大数减去小数， 互相减来减去， 一直到减数与差相等为止， 用这个相等的数字来约分。

使用步骤
第一步： 任意给定两个正整数； 判断它们是否都是偶数。若是， 则用2 约简； 若不是则执行第二步。
第二步： 以较大的数减较小的数， 接着把所得的差与较小的数比较， 并以大数减小数。继续这个操作， 直到所得的减数和差相等为止。

则第一步中约掉的若干个2 与第二步中等数的乘积就是所求的最大公约数。其中所说的" 等数 " ， 就是最大公约数。求" 等数’ 的办法是" 更相减损" 法。

实例1 : 用更相减损术求98 与63 的最大公约数。
解： 由于63 不是偶数， 把98 和63 以大数减小数， 并辗转相减：

所以， 98 和63 的最大公约数等于7 。

实例2 : 用更相减损术求260 和104 的最大公约数。
解： 由于260 和104 均为偶数，首先用2约简得到130和52，再用2约简得到65和26。此时65 是奇数而26 不是奇数， 故把65 和26 辗转相减：

所以，260与104的最大公约数等于13 乘以第一步中约掉的两个2，即13 * 2 * 2 = 52 。通常认为， 算法描述中的第一步" 可半者半之" 是指分子分母皆为偶数的时候， 首先用2 约简。因为更相减损术原先是专用来约分， 所以并不用考虑最后计算结果时， 要把第一步中约掉的若干个2 再乘回去。
加入这一步的原因可能是， 分母、分子皆为偶数是在分数加减运算的结果中比较容易遇到的一种情况， 用这种方法有可能减少数字的位数， 简化计算。当然， 省略这个以2 约简的步骤， 也能得到正确的答案。

• 朴素的算法

import time
m = int(input("m="))
n = int(input("n="))t1 = time.time()while m ％ 2 == 0 and n ％ 2 == 0 m = m / 2n = n / 2cnt = cnt + 1while m != n：if m <n:m,n = n,mm = m - nt2 = time.time()if cnt != 0 ：print("最大公约数％d,用时％.2fs"%(m*cnt*2,t2-t1))
else:print("最大公约数％d,用时％.2fs"%(m,t2-t1))

• 简化的算法

import time
m = int(input("m ="))
n = int(input("n="))
tl = time.time()
While m != n:if m > n:m = m - nelse:n = n - 1
t2 = time.time()
print("最大公约数%d ，用时%.2fs"%(m,t2-t1))

实践

4.3 辗转相除法求最大公约数

import time
m = int(input(" m = "))
n = int(input("n="))
tl = time.time()
while n != 0 ：if m > n:r = m % nm = nn = r
t2 = time.time()
print("最大公约数％d,用时％，2fs"%(m,t2-t1))