7-26 最大公约数和最小公倍数

一、题目要求

本题要求两个给定正整数的最大公约数和最小公倍数。

输入格式:

输入在一行中给出两个正整数M和N（≤1000）。

输出格式:

在一行中顺序输出M和N的最大公约数和最小公倍数，两数字间以1空格分隔。

输入样例:

511 292

输出样例:

73 2044

二、代码

1.枚举法

#include <stdio.h>
int main() {
    int a, b, c;
    scanf("%d %d", &a, &b);
    for (int i = 1; i <= a&&i<=b; i++) {
        if (a % i == 0 && b % i == 0) {
            c = i;
        }
    }
    printf("%d %d", c, a * b / c);
    return 0;
}

2.辗转相除法

利用循环：

#include <stdio.h>
int main() {
    int a, b;
    scanf("%d %d", &a, &b);
    int m = a * b;
    while (b != 0) {
        int t = a % b;
        a = b;
        b = t;
    }
    printf("%d %d", a,m/a);
    return 0;
}

 利用函数：

#include <stdio.h>
int gcd(int a, int b);
int main() {
    int a, b;
    scanf("%d %d", &a, &b);

    printf("%d %d", gcd(a, b),a*b/gcd(a, b));
    return 0;
}
int gcd(int a, int b) {
    int m;
    if (a < b) {
        int t = a;
        a = b;
        b = t;
    }
    if (a % b == 0)m = b;
    else m = gcd(b, a % b);
    return m;
}

补充：欧几里得算法/辗转相除法(引自百度百科)