用短除法求最小公倍数算法,分析算法的时间复杂度和空间复杂度,利用C语言实现

算法描述：

输入两个正整数a和b，求它们的最小公倍数。

1. 求出a和b的最大公约数gcd。
2. 最小公倍数lcm = a * b / gcd。

时间复杂度：使用短除法求最大公约数的时间复杂度为O(log(min(a,b)))，求最小公倍数的时间复杂度为O(1)，因此总时间复杂度为O(log(min(a,b)))。

空间复杂度：只需要常量级别的空间存储变量，因此空间复杂度为O(1)。

C语言实现：

#include <stdio.h>

int gcd(int a, int b) {
    if (a < b) {
        int t = a;
        a = b;
        b = t;
    }
    int r = a % b;
    while (r != 0) {
        a = b;
        b = r;
        r = a % b;
    }
    return b;
}

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

int main() {
    int a, b;
    printf("请输入两个正整数：");
    scanf("%d %d", &a, &b);
    printf("它们的最小公倍数是：%d\n", lcm(a, b));
    return 0;
}