[已解决]最大公约数和最小公倍数

pdl666

求两个给定正整数的最大公约数和最小公倍数。

最大公约数可以用辗转相除法，描述如下：

1）取两个数中最大的数做除数，较小的数做被除数

2）用最大的数除较小数，如果余数为0，则较小数为这两个数的最大公约数，如果余数不为0，用较小数除上一步计算出的余数

3）直到余数为0，则这两个数的最大公约数为上一步的余数。

最小公倍数等于两数乘积除以最大公约数




输入


输入在一行中给出两个正整数M和N(≤1000)。


输出

在一行中顺序输出M和N的最大公约数和最小公倍数，两数字间以1空格分隔。





输入样例1
511 292

输出样例1
73 2044

最佳答案

月排行榜 / 总排行榜

isdkz

2023-4-19 12:57:10

你可以使用以下的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函数用于读取输入并调用这两个函数来输出结果。

跳转到最佳答案楼层

isdkz

你可以使用以下的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函数用于读取输入并调用这两个函数来输出结果。