最大公约数

最大公约数（Greatest Common Divisor，GCD）和最小公倍数（Least Common Multiple，LCM）是数论中的两个重要概念，它们可以通过不同的算法在多种编程语言中实现。以下是一些常见编程语言中求最大公约数和最小公倍数的方法：

Python

Python内置了求最大公约数的函数math.gcd，但求最小公倍数需要自己实现或使用公式lcm(a, b) = abs(a*b) // gcd(a, b)。

import math

def gcd(a, b):
    return math.gcd(a, b)

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

# 示例
a = 12
b = 18
print(f"GCD of {a} and {b} is {gcd(a, b)}")
print(f"LCM of {a} and {b} is {lcm(a, b)}")

JavaScript

JavaScript没有内置的GCD函数，但可以使用欧几里得算法手动实现。

function gcd(a, b) {
   
    while (b !== 0) {
   
        let t = b;
        b = a % b;
        a = t;
    }
    return a;
}

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

// 示例
let a = 12;
let b = 18;
console.log(`GCD of ${
     a} and ${
     b} is ${
     gcd(a, b)}`);
console.log(`LCM of ${
     a} and ${
     b} is ${
     lcm(a, b)}`);

Java

Java的java.math包中有一个BigInteger类，它提供了gcd方法。对于最小公倍数，可以使用相同的公式。

import java.math.BigInteger;

public class GCDLCM {
   
    public static BigInteger gcd(BigInteger a, BigInteger b) {
   
        return a.gcd(b);
    }

    public static BigInteger lcm(BigInteger a, BigInteger b) {
   
        return a.multiply(b).divide(gcd(a, b));
    }

    public static void main(String[] args) {
   
        BigInteger a = new BigInteger("12");
        BigInteger b = new BigInteger("18");
        System.out.println("GCD of " + a + " and " + b + " is " + gcd(a, b));
        System.out.println("LCM of " + a + " and " + b + " is " + lcm(a, b));
    }
}

C++

C++标准库中没有直接提供GCD和LCM的函数，但可以使用递归或循环实现欧几里得算法。

#include <iostream>

int gcd(int a, int b) {
   
    return b == 0 ? a : gcd(b, a % b);
}

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

int main() {
   
    int a = 12;
    int b = 18;
    std::cout << "GCD of " << a << " and " << b << " is " << gcd(a, b) << std::endl;
    std::cout << "LCM of " << a << " and " << b << " is " << lcm(a, b) << std::endl;
    return 0;
}

C

C语言同样需要手动实现GCD和LCM。

#include <stdio.h>

int gcd(int a, int b) {
   
    return b == 0 ? a : gcd(b, a % b);
}

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

int main() {
   
    int a = 12;
    int b = 18;
    printf("GCD of %d and %d is %d\n", a, b, gcd(a, b));
    printf("LCM of %d and %d is %d\n", a, b, lcm(a, b));
    return 0;
}