PTA 编程题 -- 最大公约数和最小公倍数

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

输入格式:

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

输出格式:

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

输入样例:

511 292

输出样例:

73 2044

思路：求最大公约数的方法，目前来说最好的就是辗转相除法，也叫欧几里得算法（Euclidean Algorithm）。

例如，要计算15和24的最大公约数，首先让把较大的数赋值给p,把较小的数赋值给q，p=24,q=15;

然后计算p,q的余数，即r=p%q，显然如果r==0了，q就是能整除p的从而最大公约数就是q。如果r!=0，那么可以推导出p,q的最大公因子一定等于q,r的最大公因子。

于是从新赋值p=q,q=r, 并重复上面的步骤，直到r==0为止，这时的q就是，原p,q的最大公因子。

至于最小公倍数，它显然就是两数乘机除以最大公约数。

代码1：

int main () {
    int M,N,p,q,r;
    scanf("%d %d", &M, &N);
    p = M>N? M:N; // p是较大的
    q = M>N? N:M; // q是较小的
    r = p%q;      // r是余数
    // 以下代码就是小学奥数(或者初等数论)里讲的辗转相除法，也叫欧几里得算法（Euclidean Algorithm）
    while (r > 0) {  
        p = q;
        q = r;
        r = p%q;
    } // 最后一个非零的余数r,就是M,N的最大公约数
    printf("%d %d", q, M*N/q);  // 最小公倍数就是两数之积除以最大公约数
    return 0;
}

代码2：通常我们会把求最大公因子的代码写成一个函数，就像下面这样

#include <stdio.h>
int GCD (int M, int N) {
    int p,q,r;
    p = M>N? M:N; // p是较大的
    q = M>N? N:M; // q是较小的
    r = p%q;      // r是余数
    // 以下代码就是小学奥数学过的辗转相除法，也叫欧几里得算法（Euclidean Algorithm）
    while (r > 0) {  
        p = q;
        q = r;
        r = p%q;
    } // 最后一个非零的余数r,就是M,N的最大公约数
    return q;
}
int main () {
    int M,N,G;
    scanf("%d %d", &M, &N);
    G = GCD(M,N);
    printf("%d %d", G, M*N/G);  // 最小公倍数就是两数之积除以最大公约数
    return 0;
}

  更多PTA题目的的参考代码，可以在下面的小程序里找到哦