求两个正整数的最小公倍数

今天我们来写求解最小公倍数的程序

1.题目描述

牛客网中的题目描述是这样的

题目链接：https://www.nowcoder.com/questionTerminal/d1205615a0904bc39e9e627e7cb9e899

2.题目分析

假设两个正整数a，b；

• 最小公倍数，最小也是这两个数中的较大的一个

思路

我们可以定义一个变量，变量从这个较大的值开始，看能不能整除这两个数，如果不行，那就+1继续判断，如果不行就继续+1判断，直到可以整除这两个数，则返回最后这个数

3.代码(头脑风暴)

代码1

#include <stdio.h>
int main() {
    long a=0;
    long b=0;
    scanf("%ld %ld",&a,&b);
    long max=a>b?a:b;
    while(max%a!=0||max%b!=0){
        max++;
    }
    printf("%ld",max);
    return 0;
}

顺着这样的逻辑，我们可以写出这样的代码，看似没有问题，但是当遇到非常大的数字的时候，这个算法就显得很复杂，并不能在规定时间内运行，就像这样

究其原因，是因为我们一个一个试数字，这样的方法其实是最耗费时间的；

那有没有更快的算法呢？答案是肯定的

代码2

我们假设存在一个数字m，同时能整除a和b；假设m/a=i，m/b=j；

i的取值肯定是从1开始的，假设我们得到一个i值，这个i*a能整除b，那就说明i*a就是最小公倍数

我们发现，在代码1的逻辑中，我们求最小公倍数用了10次循环； 在这个算法中，我们只用了5次循环便找出了最小公倍数，速度提升了很多

那么我们就顺着这个逻辑写我们的代码2

#include <stdio.h>
int main() {
    long a=0;
    long b=0;
    scanf("%ld %ld",&a,&b);
    long i=1;
    while(1){
        if((i*a)%b==0){
            break;
        }
        i++;
    }
    printf("%ld",i*a);
    return 0;
}

这个时候我们发现，代码顺利通过了

可见我们这个逻辑是行得通的，至此，我们的最小公倍数问题就求解成功了

思考：为什么要用long？

我们发现，题目的输入描述范围是1-100000

而int的表示范围有限，我们通过实践发现，用int型并不能很好的实现

4.总结

我们发现，写代码不仅仅是简单的敲敲键盘，更重要的是我们的思维，我们一定要多多练习，锻炼自己的思维能力

一个优秀的程序员肯定是先思考再敲代码的，思维永远走在双手的前面，一起加油吧！小杜陪各位一起成长