计算概论问题求解答（C语言）

#include <stdio.h>

int main(void)

{

    int n, i, m, x;

    scanf("%d,%d", &m, &n);

    if (m >= n)

        for (i = 1; i <= n; i++)

        {

            x = m;

            x *= i;

            if (x % n == 0)

            {

                printf("%d", x);

                break;
            }
        }

    else

        for (i = 1; i <= m; i++)

        {

            x = n;

            x *= i;

            if (x % m == 0)

            {

                printf("%d", x);

                break;
            }
        }

    return 0;
}

#include<stdio.h>

int main()
{
    int m, n, temp, i;
    printf("Input m,n:");
    scanf("%d,%d", &m, &n);
    if(m<n)  /*比较大小，使得m中存储大数，n中存储小数*/
    {
        temp = m;
        m = n;
        n = temp;
    }
    for(i=m; i>0; i++)  /*从大数开始寻找满足条件的自然数*/
        if(i%m==0 && i%n==0)
        {/*输出满足条件的自然数并结束循环*/
            printf("%d",i);
            break;
        }
   
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
int n,m;
int gcd(int a,int b) {//也可以用  __gcd()  函数,在括号内填入a，b即可
    if(a%b==0)
        return b;
    gcd(b,a%b);
}
int main()
{
    scanf("%d,%d",&n,&m);
    printf("%d",m*n/gcd(max(m,n),min(m,n)));
    return 0;
}

我用的是是辗转相除法，也就是题中的算法
原理：
设两数为a、b(a>b)，用gcd(a,b)表示a，b的最大公约数，r=a (mod b) 为a除以b的余数，k为a除以b的商，即a÷b=kr。辗转相除法即是要证明gcd(a,b)=gcd(b,r)。

第一步:令c=gcd(a,b)，则设a=mc，b=nc

第二步:根据前提可知r =a-kb=mc-knc=(m-kn)c

第三步:根据第二步结果可知c也是r的因数

第四步:可以断定m-kn与n互质(假设m-kn=xd，n=yd (d>1)，则m=kn+xd=kyd+xd=(ky+x)d，则a=mc=(ky+x)cd，b=nc=ycd，则a与b的一个公约数cd>c，故c非a与b的最大公约数，与前面结论矛盾)，因此c也是b与r的最大公约数。

从而可知gcd(b,r)=c，继而gcd(a,b)=gcd(b,r)。

证毕。

以上步骤的操作是建立在刚开始时r≠0的基础之上的。即m与n亦互质。