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

输入格式:

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

输出格式:

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

输入样例:

511 292

输出样例:

73 2044

#include <stdio.h>
int main()
{
    int m,n,i,temp;
    int min,max;
    scanf("%d%d",&m,&n);
    if(m>0 && n>0 && m<=1000 && n<=1000)
    {
        if(m>n)
        {
            m=m^n;
            n=m^n;
            m=m^n;
        }//交换结果 [m,n]
        for(i=1;i<=m;i++)
        {
            if(m%i == 0)
            {
                temp = m/i;
                if(n%temp == 0){
                    max = temp;//最大公约数
                    break;//不要忘记找到就退出循环，否则为 1
                }
            }
        }
        i = 1;
        while(1)
        {
            temp = n*i;
            if(temp%m == 0)
            {
                min = temp;//最小公倍数
                break;
            }
            i++;
        }
        printf("%d %d\n",max,min);
    }
    return 0;
}

思路

1. 先找最大公约数再找最小公倍数。
2. 对于两个任意正整数m和n，最大公约数也就是两个数各自因子中相同的最大因子。那么这个因子一定是比m和n都小，因此先给m和n排序：只需进行比较大小并交换即可，得到[m,n]。接着对m从1开始递增取余，找到m递增的因子i，那么m/i即为对应递减的最大的因子temp。若此时这个最大因子temp能被n取余后为0，即这个对m来说最大的因子也是n的因子，那么就是m和n的最大公约数。
3. 对于两个任意正整数m和n，m和n同时是最小公倍数的因子。那么这个最小公倍数一定比m和n都大。对较大的n从i=1开始递增相乘得到temp，n相对于temp来说是因子，那么如果temp对m取余为0则说明m也是temp的因子，那么temp就是m和n的最小公约数。

本文链接：https://shengto.top/c/pat_34.html

转载时须注明出处及本声明