求最大公约数和最小公倍数：算法与代码实现

求解最大公约数和最小公倍数

本篇博客将介绍如何求解两个正整数的最大公约数(GCD)和最小公倍数(LCM)。

什么是最大公约数和最小公倍数？

最大公约数(GCD): 两个或多个整数共有约数中最大的一个。
最小公倍数(LCM): 两个或多个整数公有的倍数中最小的一个。

如何求解最大公约数？

我们可以使用**辗转相除法(欧几里得算法)**高效地求解最大公约数。

算法步骤:

取两个数中较大的数作为被除数，较小的数作为除数。
将除数除以被除数，得到余数。
如果余数为0，则除数即为最大公约数。
如果余数不为0，则将除数作为新的被除数，余数作为新的除数，重复步骤2-3。

如何求解最小公倍数？

得到最大公约数后，我们可以利用以下公式快速计算最小公倍数:

LCM(A, B) = (A * B) / GCD(A, B)

代码实现:

以下是用 Python, Java 和 C++ 实现求解最大公约数和最小公倍数的代码示例:

Python:

def gcd(a, b):
  while b:
    a, b = b, a % b
  return a

def lcm(a, b):
  return (a * b) // gcd(a, b)

# 读取输入
a = int(input('请输入第一个正整数：'))
b = int(input('请输入第二个正整数：'))

print(f'最大公约数：{gcd(a, b)}')
print(f'最小公倍数：{lcm(a, b)}')

Java:

import java.util.Scanner;

public class Main {
  public static void main(String[] args) {
    Scanner input = new Scanner(System.in);
    System.out.print('请输入第一个正整数：');
    int a = input.nextInt();
    System.out.print('请输入第二个正整数：');
    int b = input.nextInt();

    System.out.println('最大公约数：' + gcd(a, b));
    System.out.println('最小公倍数：' + lcm(a, b));
  }

  public static int gcd(int a, int b) {
    if (b == 0) {
      return a;
    }
    return gcd(b, a % b);
  }

  public static int lcm(int a, int b) {
    return (a * b) / gcd(a, b);
  }
}

C++:

#include <iostream>
using namespace std;

int gcd(int a, int b) {
  while (b != 0) {
    int temp = a % b;
    a = b;
    b = temp;
  }
  return a;
}

int lcm(int a, int b) {
  return (a * b) / gcd(a, b);
}

int main() {
  int a, b;
  cout << '请输入第一个正整数：';
  cin >> a;
  cout << '请输入第二个正整数：';
  cin >> b;

  cout << '最大公约数：' << gcd(a, b) << endl;
  cout << '最小公倍数：' << lcm(a, b) << endl;
  return 0;
}

通过以上代码，您可以轻松计算任意两个正整数的最大公约数和最小公倍数。