最大公约数和最小公倍数

Question

最大公约数和最小公倍数

本题目要求读入2个正整数A和B，然后输出它们的最大公约数和最小公倍数。

输入格式:
输入在一行中给出2个不超过10000的正整数A和B。

输出格式:
对每一组输入，在一行中输出最大公约数和最小公倍数，用逗号分隔。

输入样例:
2 3
输出样例:
1,6

Answer 1

首先，最大公约数，也就是最大公因数，即最大的、可以同时整除m和n的数
那么，首先，一个数的因数有1和它本身
所以两个数的最大公因数，肯定是小于等于两个数中较小的那个数的
等于较小的那个数的时候，说明m和n是倍数关系
而最小公倍数，有一个计算公式，
最小公倍数=(m*n)/最大公约数

那么我们先求最大公约数
由于最大公约数肯定小于等于m和n较小的那个数，所以先把较小的数得到
之后，与求素数类似的
我们从这个数开始，看这个数能否同时对m和n整除，若可以，那么它就是最大公约数，若不能，对其减一，在下一次循环中再次判断是否可以整除m和n
也可以直接使用我们之前说到的，使用这两个数与他们的最大公因数求最小公倍数的公式

#include<stdio.h>
int main()
{
    int m = 0;
    int n = 0;
    scanf("%d %d", &m, &n);//输入两个数
    int i = 0;//使用i来存储较小的那个数，并在后续用作循环
    if (m > n)//将两个数中较小的那个赋值给i，此处可以使用三目运算符代替
    {
        i = n;
    }
    else
    {
        i = m;
    }

    for (; i >= 1; i--)//此处i已经在上边的if中有一个初值了，所以在这里的循环中可以不进行初始化，所以空着
    {
        if (m % i == 0 && n % i == 0)//判断本次循环中的i能否整除m和n
        {
            //若能整除，结束循环，此时的i就是最大公约数
            break;
        }
    }
    //循环结束的时候，i是最大数公约数
    printf("最大公约数是： % d\n", i);
    //使用公式，计算最小公倍数并输出
    printf("最小公倍数是： % d", (m * n) / i);
}