最大公因数与最小公倍数

思路

给两个正整数,求它们的最大公因数(GCD)和最小公倍数(LCM)。

最大公因数

欧几里得算法(辗转相除法):,当

最小公倍数

有公式:

为了防止溢出,先除再乘:a / gcd * b

代码

#include <iostream>
using namespace std;
int main() {
    long long a, b;
    cin >> a >> b;
    long long x = a, y = b;
    while (y) { long long t = y; y = x % y; x = t; }
    cout << x << " " << a / x * b << endl;
    return 0;
}
import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long a = sc.nextLong(), b = sc.nextLong();
        long x = a, y = b;
        while (y != 0) { long t = y; y = x % y; x = t; }
        System.out.println(x + " " + (a / x * b));
    }
}
import math

a, b = map(int, input().split())
g = math.gcd(a, b)
print(g, a // g * b)
const readline = require('readline');
const rl = readline.createInterface({ input: process.stdin });
const lines = [];
rl.on('line', line => lines.push(line));
rl.on('close', () => {
    const parts = lines[0].trim().split(/\s+/);
    let a = BigInt(parts[0]), b = BigInt(parts[1]);
    function gcd(x, y) {
        while (y) { [x, y] = [y, x % y]; }
        return x;
    }
    const g = gcd(a, b);
    console.log(g.toString() + " " + (a / g * b).toString());
});

复杂度

  • 时间复杂度,欧几里得算法的迭代次数。
  • 空间复杂度