大家好，又见面了，我是你们的朋友全栈君。
目录
一.思路分析
1.欧几里得法(辗转相除法)
2.穷举法(一个一个除)
3.stein算法
二.提高要求
三.测试截图
题目：求两个正整数的最大公约数和最小公倍数。
基本要求：1.程序风格良好(使用自定义注释模板)，两种以上算法解决最大公约数问题，提供友好的输入输出。
提高要求：1.三种以上算法解决两个正整数最大公约数问题。
2.求3个正整数的最大公约数和最小公倍数。
一.思路分析
因为之前接触过这个问题，所以自己是知道欧几里得算法和穷举法计算最大公约数，在求出两个数的最大公约数之后，便可以利用lcm(a,b) = (a*b)/gcd(a,b) 计算出两个数的最小公倍数。之后还上网查了一下stein算法，最后在理解stein算法的基础上解决了这个问题。下面我会一一对这几种算法进行分析：
1.欧几里得法(辗转相除法)
这条算法基于一个定理：两个正整数a和b（a>b），它们的最大公约数等于a除以b的余数c和b之间的最大公约数。比如10和25，25除以10商2余5，那么10和25的最大公约数，等同于10和5的最大公约数。
基于这条定理：
首先，我们先计算出a除以b的余数c，把问题转化成求出b和c的最大公约数；然后计算出b除以c的余数d，把问题转化成求出c和d的最大公约数；再然后计算出c除以d的余数e，把问题转化成求出d和e的最大公约数……以此类推，逐渐把两个较大整数之间的运算简化成两个较小整数之间的运算，直到两个数可以整除，或者其中一个数减小到1为止。贴代码：
代码语言：javascript复制# -*- coding:utf-8 -*-
# @Author: Jiawei Han
def first_way(a, b):
"""
第一种方法：欧几里得算法----辗转相除法
:param a: 第一个数
:param b: 第二个数
:return: 最大公约数
"""
# 如果最终余数为0 公约数就计算出来了
while(b!=0):
temp = a % b
a = b
b = temp
return a2.穷举法(一个一个除)
这个比较好理解。因为a,b两个数的最大公因数肯定小于等于相对更小的那个数，所以从两个数中较小数开始由大到小列举，直到找到公约数立即中断列举，得到的公约数便是最大公约数 。代码如下：
代码语言：javascript复制def second_way(a, b):
"""
第二种方法：一个一个除
:param a: 第一个数
:param b: 第二个数
:return: 最大公约数
"""
# 保证a>b
if(a<b):
a,b = b,a
for i in range(1,b 1):
if (a%i==0) and (b%i==0):
value = i;
return value3.stein算法
看下面这两个结论
gcd(a, a) = a， 也就是一个数和他自己的公约数是其自身。
gcd(ka, kb) = k * gcd(a, b)，也就是最大公约数运算和倍乘运算可以交换，特殊的，当k=2时，说明两个偶数的最大公约数比如能被2整除。
代码语言：javascript复制def third_way(a,b):
"""
第三种方法思想：stein算法
gcd(a,a)=a，也就是一个数和其自身的公约数仍是其自身。
gcd(ka,kb)=k gcd(a,b)，也就是最大公约数运算和倍乘运算可以交换。特殊地，当k=2时，说明两个偶数的最大公约数必然能被2整除。
当k与b互为质数，gcd(ka,b)=gcd(a,b)，也就是约掉两个数中只有其中一个含有的因子不影响最大公约数。特殊地，当k=2时，说明计算一个偶数
和一个奇数的最大公约数时，可以先将偶数除以2。
:param a: 第一个数
:param b: 第二个数
:return: 最大公约数
"""
#保证b比a小
if a < b:
a, b = b, a
if (0 == b):
return a
# a,b都是偶数 除2右移一位即可
if a % 2 == 0 and b % 2 == 0:
return 2 * third_way(a >> 1, b >> 1)
# a是偶数
if a % 2 == 0:
return third_way(a >> 1, b)
# b是偶数
if b % 2 == 0:
return third_way(a, b >> 1)
# 都是奇数
return third_way((a b) >> 1, (a - b) >> 1)求出a,b的最大公约数后，利用lcm(a,b) = (a*b)/gcd(a,b) 计算出两个数的最小公倍数：
代码语言：javascript复制# 求两个数的最小公倍数
def lcm(a,b):
return a * b / third_way(a, b)二.提高要求
计算三个数的最大公约数时，我是利用之前写好的计算2个数的最大公约数的方法，先算出a,b的公约数，再用a,b的公约数与c再代入方法，此时返回的值就是三个数的最大公约数了。
同样，在计算三个数的最小公倍数时，多次嵌套，先求出两个数的最小公倍数，再求其与第三个数的最小公倍数。
代码语言：javascript复制def three_num(a,b,c):
"""
求三个数的最大公约数
:param a: 第一个数
:param b: 第二个数
:param c: 第三个数
:return: 这三个数的最大公约数
"""
# 多次嵌套，返回3个数的最大公约数
return first_way(first_way(a,b),c)a,b,c =map(int,input("请输入需要计算的整数用空格隔开：").split())
print("这三个数的最大公约数是：" str(three_num(a,b,c)))
# 我这里使用多次嵌套，先求出两个数的，再求与第三个数的最小公倍数
print("这三个数的最小公倍数是：" str(lcm(a,b)*c/third_way(third_way(a,b),c)))main方法：
代码语言：javascript复制if __name__ == '__main__':
flag = input("请选择功能：n 1.计算两个数的最大公约数和最小公倍数n 2.计算三个数的最大公约数和最小公倍数n")
if flag=='1':
a,b = map(int,input("请输入需要计算的整数用空格隔开：").split())
print("这两个数的最大公约数为" str(third_way(a, b)))
val = lcm(a, b)
# 利用最大公约数求最小公倍数
print("最小公倍数为：" str(val))
elif flag=='2':
a,b,c =map(int,input("请输入需要计算的整数用空格隔开：").split())
print("这三个数的最大公约数是：" str(three_num(a,b,c)))
# 我这里使用多次嵌套，先求出两个数的，再求与第三个数的最小公倍数
print("这三个数的最小公倍数是：" str(lcm(a,b)*c/third_way(third_way(a,b),c)))
else:
print("请输入正确序号")三.测试截图
求两个数的：
求三个数的：
发布者：全栈程序员栈长，转载请注明出处：https://javaforall.cn/145747.html原文链接：https://javaforall.cn
