输入两个正整数a和b,求其最大公约数和最小公倍数。
输入格式:输入在一行中给出2个不超过100000的正整数A和B。
输出格式:在2行中输出A、B的最大公约数和最小公倍数。
输入样例:输出样例:42 36
最大公约数为:6
最小公倍数为:252
代码(Python):
方法一(比较容易理解):
a,b=map(int,input().split()) #两个数的输入
d=max(a,b) #用Python内置函数找出两个数中较大的
x=min(a,b) ##用Python内置函数找出两个数中较小的
#求最大公约数
for i in range(x,0,-1): #因为最大公约数一定比两个数都小,且求的是公约数中的最大值,所以从较小的数开始一直尝试到0(不包括0),因为是倒着往前试,所以步长置为-1
if a%i==0 and b%i==0: #如果遇到了可以被两个数同时整除的数,那它一定是最大公约数,则break退出循环
print("最大公约数为:%d"%i) #按格式输出
break #退出循环
#求最小公倍数
for i in range(d,a*b+1): #因为最小公倍数一定比两个数都大,且求的是公倍数中的最小值,所以从较大的那个数一直开始尝试到a*b,因为a*b一定是他俩的公倍数,且最小公倍数一定小于等于a*b
if i%a==0 and i%b==0: #如果遇到可以同时整除两个数的,那它一定是最小公倍数
print("最小公倍数为:%d"%i) #按格式输出
break #退出循环
方法二:
a,b=map(int,input().split()) #注意这里不能是a=int(input()) b=int(input())因为input会读取一行中的所有字符串
m=a #先把a,b的值记录下来,以防下面的将a,b的值改变后使a,b真正的值丢失
n=b
res=m%n #求最大公约数先将两数相除取余
while(res!=0): #判断余数是否为0,若为0则除数就是最大公约数
a=b #若不为0,则将除数的值赋给被除数,将余数的赋给除数
b=res
res=a%b #继续相除,准备进入下一次循环
x1=b #用来存放最终除数的值,即最大公约数
x2=m*n/x1 #根据一个数学公式,即最小公倍数等于两数乘积再除以最大公约数
print("最大公约数为:%d"%x1) #按格式输出
print("最小公倍数为:%d"%x2)
上面给出大家两种求最大公约数和最小公倍数的方法,大家可以根据自己的情况选取不同的方法,鼓励大家两种方法都掌握哦!
上面的程序给出了比较详细的注释,以便新手小白参考。程序的思路设计或者代码实现并不是最优的,欢迎各位大佬指正错误或者给出更优质的思路。
我是一只想成为鲲鹏的菜鸟,大家的鼓励是我前进的动力,欢迎大家点赞收藏评论哦!
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)