最大公约数和最小公倍数
求两个给定正整数的最大公约数和最小公倍数。最大公约数可以用辗转相除法，描述如下：
1）取两个数中最大的数做除数，较小的数做被除数
2）用最大的数除较小数，如果余数为0，则较小数为这两个数的最大公约数，如果余数不为0，用较小数除上一步计算出的余数
3）直到余数为0，则这两个数的最大公约数为上一步的余数。
最小公倍数等于两数乘积除以最大公约数
输入
输入在一行中给出两个正整数M和N(≤1000)。
输出
在一行中顺序输出M和N的最大公约数和最小公倍数，两数字间以1空格分隔。
输入样例1
511 292
输出样例1
73 2044
你可以使用以下的Python代码来实现这个问题的解决方案：
def gcd(a, b):
while b:
a, b = b, a % b
return a
def lcm(a, b):
return a * b // gcd(a, b)
def main():
M, N = map(int, input().strip().split())
print(gcd(M, N), lcm(M, N))
if __name__ == "__main__":
main()
这个程序定义了两个函数gcd和lcm，分别用于计算最大公约数和最小公倍数。gcd函数使用辗转相除法，lcm函数利用两数乘积除以最大公约数的性质计算最小公倍数。main函数用于读取输入并调用这两个函数来输出结果。
页:
[1]