最大公因数与最小公倍数
思路
给两个正整数,求它们的最大公因数(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());
});
复杂度
- 时间复杂度:
,欧几里得算法的迭代次数。
- 空间复杂度:
。



京公网安备 11010502036488号