首页 > 试题广场 >

求最小公倍数

[编程题]求最小公倍数

热度指数：371380 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

$\hspace{15pt}$ 对于给定的两个正整数 $a,b$ ，它们的最小公倍数 $\operatorname{lcm}(a,b)$ 是指能同时被 $a$ 和 $b$ 整除的最小正整数。
$\hspace{15pt}$ 求解 $\operatorname{lcm}(a,b)$ 。

输入描述:

在一行上输入两个整数 。

输出描述:

输出一个整数，表示 。

示例1

输入

5 7

输出

示例2

输入

2 4

输出

算法知识视频讲解

BugMagic

#include <stdio.h>

int main() {
    int a, b,ans,i=2;

    scanf("%d %d", &a, &b);
    ans=a*b;

    while(i<=a || i<=b)
    {
        if(a%i==0 && b%i==0)
        {
            a/=i;b/=i;ans/=i;
        }
        else i++;
    }
    
    printf("%d",ans);
    return 0;
}

发表于 2025-03-03 15:53:50 回复(1)

唐凌Zero

用欧几里得算法可以快速求最大公约数（GCD），两数之积除以最大公约数就是最小公倍数：

#include <stdio.h>

int gcd(int a,int b)
{
    while(b)
    {
        const int t=b;
        b=a%b;
        a=t;
    }
    return a;
}

int main()
{
    int a, b;
    while (scanf("%d %d", &a, &b) != EOF)
    {
        int f=gcd(a,b);
        printf("%d\n",a*b/f);
    }
    return 0;
}

发表于 2024-08-17 08:19:39 回复(0)

牛客58982666号

#include <stdio.h>

int main() {

int a, b;

int x;

while (scanf("%d %d", &a, &b) != EOF) { // 注意 while 处理多个 case

x=a*b;

for (int i=1;i<x; i++) {

if (i%a==0&&i%b==0) {

printf("%d",i);

break;

}

return 0;

}

为什么加上i<x就不行了呢，不加就可以

编辑于 2024-04-02 17:29:36 回复(1)

Helljumper

//遍历法求最小公倍数
#include "stdio.h"
int main()
{
    int a ,b ,i,c;
    scanf("%d %d", &a, &b);
    for(i = 1; i <= a; i++)
    {
        if(a % i ==0 && b % i == 0)//此时i为最大公约数
        {
                c = i;
        }
    }
    printf("%d", (a * b) / c);
    //注意输出最小公倍数不能放在for里面，否则（如果需要多次循环）会多次输出。外面也不能直接用i进行计算（因为会继续运算加上去，直到不满足i<=a的条件）,需要用一个额外的变量在if里来暂存i。
    //公约数显然是能让两个数都对其取余的结果==0；经过i一直往上加，并将最符合要求的放入c可得到最大公约数。i必须从1开始遍历，理由是互质数的最大公约数就是1；两数中较大的一方为最小公倍数时，使用此法仍可以正确地得到最大公因数和最小公倍数。
   return 0;
}

编辑于 2024-03-26 00:50:21 回复(0)

彭洋a

#include <stdio.h>

int main() {

int a, b;

while (scanf("%d %d", &a, &b) != EOF) {

int min = a<b?a:b;

int ret = 1;

for(int i = 2;i<min;i++)

{

while(a%i==0&&b%i==0)

{

ret *= i;

a /= i;

b /= i;

}

ret *= a*b;

printf("%d\n",ret);

}

return 0;

}

发表于 2023-10-11 09:16:41 回复(0)

我不叫李大侠

#include <stdio.h>

int main() {

int a,b;

scanf("%d %d", &a, &b);

int n = 1;

while (1) {

if (n % a == 0 && n % b == 0) {

break;

}

n++;

}

printf("%d\n", n);

return 0;

}

发表于 2023-08-17 15:57:56 回复(0)

时光^_^

#include<stdio.h> 

int main()
{
    int A = 0;
    int B = 0;
    scanf("%d %d", &A, &B);
    int m = (A > B ? A : B);
    while (m % A != 0 || m % B != 0)
    {
        m++;
    }
    printf("%d", m);
    return 0;
}

我这个思路是将其中大的数作为标准，进行加一，直到能同时除以A，B时，不进行加一。

#include<stdio.h> 

int main()
{
    int A = 0;
    int B = 0;
    scanf("%d %d", &A, &B);
    int i = 1;
    while (A * i % B != 0)
    {
        i++;
    }
    printf("%d", A * i);
    return 0;
}

这个代码是简化版，因为上一个是加一太慢了，我们采用一种倍数的关系来解决。首先m / a = i; a * i % b == 0. 所以a * i % b == 0时就代表是公倍数了。

发表于 2022-12-01 20:18:47 回复(0)

Triiiiiista

#include<stdio.h>
int main()
{
    int a,b,out=1;
    
    int j=0;
    scanf("%d",&a);
    scanf("%d",&b);
    int a1,b1;
    a1=a;
    b1=b;
    if(a>b)
    {
        if(a%b==0)
            out=a;
        else if(a%b)
        {
            for(int i=2;i<b;i++)
            {
                while(a%i==0&&b%i==0)
                {
                    a=a/i;
                    b=b/i;
                    i=2;
                }
            }
            out=a*b1;
        }
    }
    else if(a<b)
    {
        if(b%a==0)
            out=b;
        else if(b%a)
        {
            for(int i=2;i<a;i++)
            {
                while(a%i==0&&b%i==0)
                {
                    a=a/i;
                    b=b/i;
                    i=2;
                }
            }
            out=a*b1;
        }
    }
    else
        out=a;
    printf("%d",out);
    return 0;
}

发表于 2022-08-22 10:57:12 回复(0)

牛客239147792号

#include<stdio.h>
int main()
{
int a,b,c,n,m;
scanf("%d %d", &a, &b);
if(a<b)
{
c=b;
b=a;
a=c;
}
if(a%b==0)
printf("%d",a);
else {
for(n=1;n<=b;n++)
{
m=a*n;
if(m%b==0)
{
printf("%d",m);
break;
}
}
}
}

发表于 2022-04-18 18:39:21 回复(0)

牛客285843472号

#include<stdio.h>
int main() {
int a, b, count = 0;
scanf("%d%d", &a, &b);
do {
count++;
} while (!(count % a == 0 && count % b == 0));
printf("%d", count);
return 0;
}

发表于 2022-04-07 17:10:36 回复(0)

长住

int main() {
    int a = 0;
    int b = 0;
    int i = 1;
    scanf("%d %d", &a, &b);
    while ((i*a)%b!=0)
    {
        i++;
    }
    printf("%d", i * a);

    return 0;
}

发表于 2021-11-29 17:50:12 回复(0)

牛客489027493号

//暴力解

#include <stdio.h>
int main(void)
{
int a = 0;
int b = 0;
scanf("%d%d", &a, &b);

for (int i = (a > b) ? b : a; i <= a * b; i++) {
if (i % a == 0 && i % b == 0) {
printf("%d\n", i);
break;
}
}
}

发表于 2021-09-20 15:19:47 回复(0)

牛客421028605号

//goto 语句用于判断最小公倍数是否能被整除多次，暂时没想到好的算法了。。
#include<stdio.h>
int main()
{
    int a,b,max;
    int sum=1;
    scanf("%d %d",&a,&b);
    int i;
    if(a>b)
        max=a;
    else
        max=b;
    out:
    for(i=2;i<=max;i++)
    {
        if((a%i==0)&&(b%i==0))
        {
            a/=i;
            b/=i;
            sum*=i;
            goto out;
        }
    }
    sum=sum*a*b;
    printf("%d",sum);
}

发表于 2021-09-01 21:36:28 回复(0)

Xxiang07

#include <stdio.h>

int main()
{
int m,n,re;
scanf("%d %d",&m,&n);

int temp = m*n;
while(temp>=m && temp>=n)
{
if((temp%n == 0) && (temp%m == 0))
{
re = temp;
}
temp --;
}

printf("%d",re);

return 0;
}

发表于 2021-08-31 01:36:23 回复(0)

牛客415544593号

#include<stdio.h>

int main()
{
    int a,b;
    scanf("%d %d",&a,&b);
    for(int i=a;i<=a*b;i++)
    {
        if(i%a==0 && i%b ==0)
        {
            printf("%d",i);
            break;
        }
    }
    return 0;
}

发表于 2021-08-16 23:09:58 回复(0)

80后大叔

#include<stdio.h>
int main(){
    int a,b,maxGY;
    scanf("%d %d",&a,&b);
    //先求出最大公约数
    for(int i=a>b?a:b; i>=1;i--){
        if(a%i==0&&b%i==0){
            maxGY=i;
            break;
        }
    }
    //最小公倍数=a*b/最大公约数
    printf("%d\n",a*b/maxGY);
}

发表于 2021-08-08 12:28:28 回复(0)

电源

#include <stdio.h>
int main()
{
int a,b,beishu=1;
scanf("%d",&a);
scanf("%d",&b);
beishu=a*b;
while(a!=b)//更相减损术
{
if(a>b)
a=a-b;
else b=b-a;
}
beishu=beishu/a;
printf("%d",beishu);
return 0;
}

发表于 2021-07-26 15:19:41 回复(0)