求两个非负整数的最大公约数和最小公倍数

Question

求两个非负整数的最大公约数和最小公倍数
求两个非负整数的最大公约数和最小公倍数
求两个非负整数的最大公约数和最小公倍数

Answer 1

让阿豪来帮你解答，本回答参考chatgpt3.5编写提供，如果还有疑问可以评论或留言

1. 首先需要明确最大公约数和最小公倍数的概念：

• 最大公约数：两个数中能够同时整除的最大正整数，常用符号为gcd；
• 最小公倍数：两个数的公倍数中最小的正整数，常用符号为lcm。
• 最大公约数可以使用辗转相除法（欧几里得算法）来求解，具体步骤如下：
• 把两个数按照大小排列，设较小的数为a，较大的数为b；
• 用b除以a，得到商q和余数r，即b=q*a+r；
• 如果余数r为0，那么a就是最大公约数；
• 如果余数r不为0，则继续用a除以r，得到商q'和余数r'，即a=q'*r+r'；
• 重复上述过程，直到余数r为0为止。 例如，求36和24的最大公约数：
• 把36和24按照大小排列，36 > 24，所以a=24，b=36；
• 用36除以24，得到商1，余数12，即36=1*24+12；
• 用24除以12，得到商2，余数0，即24=2*12+0；
• 因为余数为0，所以12就是最大公约数，即gcd(36,24)=12。
• 最小公倍数可以通过最大公约数来求解，具体公式为： lcm(a,b) = a*b / gcd(a,b)。 例如，求36和24的最小公倍数：
• 先求它们的最大公约数，得到gcd(36,24)=12；
• 然后带入公式，lcm(36,24) = 36*24 / 12 = 72；
• 所以36和24的最小公倍数为72，即lcm(36,24)=72。
• 代码实现：

# 定义一个函数，输入两个数，返回它们的最大公约数和最小公倍数
def gcd_lcm(a, b):
    # 首先找到两个数中较小的一个
    if a > b:
        a, b = b, a
        
    # 求最大公约数
    while b % a != 0:
        a, b = b % a, a
    gcd = a
    
    # 求最小公倍数
    lcm = a * b / gcd
    
    # 返回结果
    return gcd, lcm
# 测试一下
print(gcd_lcm(36, 24))  # 输出：(12, 72)