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

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

输入格式:

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

输出格式:

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

输入样例:

511 292

输出样例:

73 2044

#include <stdio.h>

int MCF( int x, int y );  // 最大公因数
int MCM( int x, int y );  // 最小公倍数

int main(){
    int M, N;
    
    do{ // 保证 正整数M和N（≤1000）
        scanf("%d %d", &M, &N);
    }while( M <= 0 || N <= 0 && M > 1000 || N > 1000 );
    
    // 保证(A,B)中，A始终大于B
    if( M > N )
        printf("%d %d\n", MCF(M, N), MCM(M, N));
    else 
        printf("%d %d\n", MCF(N, M), MCM(N, M));
    
    return 0;
}

int MCF( int x, int y ){
    int temp = 1;
    
    // 辗转相除法
    while( temp ){
        temp = x % y;
        x = y;
        y = temp;
    }
    
    return x;
}

int MCM( int x, int y ){
    /* 例如：3*7 
            应该从7开始计数，最大不超过21
    */
    for( int i=x; i<=x*y; i++ ){
        if( i%x==0 && i%y==0 )
            return i;
    }
}

图片素材取自百度百科：最大公约数