前言
相信大家都刷到过这种题吧，输入两个数，求出两个数的最小公倍数，我总结归纳了三种方法，希望能帮到大家。
方法一
#include<stdio.h> void min(int a,int b) { long long max = (a > b ? a : b); for (max; max <= a * b; max++) if (max % a == 0 && max % b == 0) break; printf("%lld", max); } int main() { int a = 0; int b = 0; scanf("%d %d", &a, &b); min(a, b); return 0; }
我们都知道，最小公倍数是大于等于两个数的较大数，小于等于两数相乘。
因此先求出两个数的最大值，再在最大值的基础上依次加一，来找出最小公倍数。
方法二
#include<stdio.h> void min(int a, int b) { int m = (a < b ? a : b); for (m; m > 0; m--) if (a % m == 0 && b % m == 0) break; //求出最大公约数 m long long p = a * b / m; printf("%lld", p); } int main() { int a = 0; int b = 0; scanf("%d %d", &a, &b); min(a, b); return 0; }
我们知道最大公倍数还可以利用两数相乘再除以最大公约数来求，我们利用两数的最小值来依次减一，来找到最大公约数。
当然了，我们也可以用辗转相除法来求出最大公约数，代码如下：
#include<stdio.h> void min(int a, int b) { int m = a; //先将 a , b 存起来 int n = b; while (a % b) //辗转相除，最后 b 即为最大公约数 { int f = a % b; a = b; b = f; } long long p = m * n / b; printf("%lld", p); } int main() { int a = 0; int b = 0; scanf("%d %d", &a, &b); min(a, b); return 0; }
方法三（最优解）
我们先来理一下思路吧，假设 k 是最小公倍数，那么下面两个式子必然成立，
k / a = i
k / b = j
那么我们可以推出 —> a * i % b=0
那么我们可以将 i 从 1 开始加起直到满足上式，即可求出最小公倍数为 a * i
我们可以写出如下代码：
#include<stdio.h> int main() { long long a = 0; long long b = 0; scanf("%lld %lld", &a, &b); int i = 1; while (a * i % b) { i++; } printf("%lld", a * i); return 0; }
以上便是本期全部内容了，如果对您有帮助还请多多支持哦，文章有误还请批评指出，下期见啦~
