首页 > 试题广场 >

最小公倍数

[编程题]最小公倍数
  • 热度指数：3286 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 128M，其他语言256M
  • 算法知识视频讲解

求两个数的最小公倍数，两个数的最小公倍数为：能被这两个数同时整除的最小的数。


输入描述:
输入两个整数n,m。。
答案确保在int范围以内。


输出描述:
输出两个数的最小公倍数。
示例1

输入

6 4

输出

12
示例2

输入

6 5

输出

30
算法知识视频讲解
添加回答
C/C++
猫猫猫1头像 猫猫猫1
#include<bits/stdc++.h>
usingnamespacestd;
 
longlongGCD(longlongn,longlongm){
    if(m==0){
        returnn;
    }
    else{
        returnGCD(m,n%m);
    }
}
 
intmain(){
    longlongn,m;
    while(cin>>n>>m){
        longlongk=m*n;
        cout<<k/GCD(n,m)<<endl;
    }
    return0;
}

发表于 2022-10-06 16:58:20 回复(0)
夜微雨头像 夜微雨
最小公倍数=两个数的乘积/最大公约数
注意: 不能直接用a*b/最大公约数,因为a*b很可能溢出,可以修改下:a/最大公约数*b. 
#include<iostream>
using namespace std;
//求最大公约数 使用辗除法
int gcd(int a,int b)
{
    int tmp;
    while(b)
    {
        tmp = a%b;
        a = b;
        b =tmp;
    }
    return a;
}
int main()
{
    //最小公倍数=两个数的乘积/最大公约数
    int a,b;
    cin>>a>>b;
    cout << a/gcd(a,b)*b <<endl; //注意:小心x*y直接溢出大于最大范围.
    return 0;
}
或者: 
#include<iostream>
using namespace std;
//求最大公约数  相减法
int gcd(int a,int b)
{
    while(a != b)
    {
        if( a > b)
            a = a - b;
        else
            b = b - a;
    }
    return a;
}
int main()
{
    //最小公倍数=两个数的乘积/最大公约数
    int a,b;
    cin>>a>>b;
    cout << a/gcd(a,b)*b <<endl; //注意:小心x*y直接溢出大于最大范围.
    return 0;
}

发表于 2019-11-14 19:28:32 回复(0)
Java
Boss这里有只熊头像 Boss这里有只熊
import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextInt()) { // 注意 while 处理多个 case
            int a = in.nextInt();
            int b = in.nextInt();
            int gcd = GCD(a, b);
            System.out.println((a / gcd) * b);
        }
    }

    public static int GCD(int a, int b) {

        if (b == 0) {
            return a;
        }
        return GCD(b, a % b);

    }
}
发表于 2023-09-09 21:09:24 回复(0)
牛客140240850号头像 牛客140240850号
int main()
{
    int a = 0;
    int b = 0;
    scanf("%d %d", &a, &b);
    int i = 1;
    while (i)
    {
        if (a*i % a == 0 && a*i % b == 0)
        {
            printf("%d\n", i*a);
            break;
        }
        i++;
    }
    return 0;
}
发表于 2021-03-26 20:46:26 回复(0)
C/C++
爱看电影的三文鱼在等offer头像 爱看电影的三文鱼在等offer

int main()

{

int a , b ;

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

int i = 1;

while ((a * i) % b != 0)

{

        i++;

}

printf("%d\n", i * a);

return 0;

}

编辑于 2023-08-09 12:49:02 回复(0)
牛客682666874号头像 牛客682666874号 
Scanner in = new Scanner(System.in);
        int a=in.nextInt();
        int b=in.nextInt();
        if(a>b){
            int tmp=a;
            a=b;
            b=tmp;
        }
        ArrayList<Integer> ar=new ArrayList<>();
        for(int i=a;i>1;i--){
            if(a%i==0&&b%i==0){
                a/=i;
                b/=i;
                ar.add(i);
            }
        }
        int res=a*b;
        for(int i=0;i<ar.size();i++){
            res*=ar.get(i);
        }
        System.out.println(res);
今天华泰证券笔试，我这道题这么写的值过了83%大佬们帮看看哪里有问题

发表于 2023-07-28 00:12:54 回复(0)
C/C++
auto丶头像 auto丶
以最小变量为根  一直累加 
    
#include <iostream>
using namespace std;

int main() {
    int a,b;
    cin>>a>>b;
    int num =min(a,b);
    int ma=max(a,b);
    int i=num;
    while(num%ma!=0){
        num+=i;
    }
    cout<<num;
    return 0;    
}


发表于 2023-07-18 17:02:21 回复(0)
章鱼哥~头像 章鱼哥~ 
#include <stdio.h>

int main() {
    long long int a, b;
    scanf("%lld %lld", &a, &b);
    long long int tmp = a*b;
    //确保 a 大于 b
    if (b > a)
    {
        a = a^b;
        b = a^b;
        a = a^b;
    }
    while(b != 0)
    {
        a = a%b;
        if (a == 0)  //a 等于 b 的情况
            {
                a = b;
                break;
            }
        b = b%a;
    }
    a = tmp /a; 
    printf("%lld", a);
    return 0;
}

发表于 2023-05-24 22:24:01 回复(0)
一条余弦Cos头像 一条余弦Cos
两种方法：
1、辗转相除的最大公约数，最小公倍数=两数乘积/最大公约数
2、从两者较大的数开始遍历，当找到正好能同时整除两个数时，即得到两数的最小公倍数 
#include <iostream>
using namespace std;
int GCD(int a,int b)
{
    int temp=0;
    while(b)//辗转相除法求最大公约数
    {
        temp=a%b;
        a=b;
        b=temp;
    }
    return a;  //a为最终的最大公约数
}
int main()
{
    int m,n;
    int gcd,ret;
    while(cin>>m>>n)
    {
        gcd=GCD(m,n);
        ret=m/gcd*n;  //此处的m*n可能会溢出
        cout<<ret<<endl;
    }
    
    return 0;
}



//此方法可能复杂度过大运行时间长
//#include <iostream>
//using namespace std;
//int main()
//{
//    int A,B,temp;
//    while(cin>>A>>B)//循环输入
//    {
//       for((A>B)? temp=A :temp=B; ;temp++)//找能被AB同时整除的/.最小正整数temp
//        {
//            if((temp%A==0) && (temp%B==0))
//                break;
//        }
//        cout<<temp<<endl;//输出最小公倍数
//    }
//    return 0;
//}


发表于 2020-12-02 16:12:54 回复(0)
风吹不过的夏天头像 风吹不过的夏天
#include <bits/stdc++.h>
using namespace std;
vector<int> v;
int GCD(int a,int b){
    if(b==0)
        return a;
    else
        return GCD(b,a%b);
}
int main(){
    int a,b;
    while(cin>>a>>b){
        cout<<a/GCD(a,b)*b<<endl;
    }
}

发表于 2020-07-18 22:36:06 回复(0)
C/C++
一城烟雨柳色青头像 一城烟雨柳色青 
#include<iostream>
#include <utility>
using namespace std;
int GCB(int a, int b)
{
    if(a < b)
        swap(a,b);
    int i = b;
    for(; b > 0; --i)
    {
        if(a%i == 0 && b%i == 0)
            break;
    }
    return i;
}
int main()
{
    int A,B;
    cin >> A >> B;
    cout << ((A/GCB(A,B)) * (B/GCB(A,B))* GCB(A,B)) << endl;
    return 0;
}

发表于 2020-06-09 16:05:13 回复(0)
C/C++
cornfieldchase头像 cornfieldchase 
/***************************************************
 * Author        : cornfieldchase
 * Blog          : cornfieldchase2014.com
 * Filename      : 求最小公倍数.cpp
 * Description   : 
 * Last modified : 2019-11-14 18:45
***************************************************/
#define _CRT_SECURE_NO_WARNINGS 1
#include <iostream>
using namespace std;
int main()
{
	int m, n, i;
	cin >> m >> n;
	for (i = m;; i++)
	{
		if (i%m == 0 && i%n == 0)
			break;
	}
	cout << i;
}

发表于 2019-11-14 18:54:13 回复(0)
残钺头像 残钺 
package main
import "fmt"
func main(){
	var m ，n ，a ，c int 
	fmt.Scanln(&m,&n)
	c=m*n
	if m<n{
		m,n=n,m
	}
	for n!=0{
		a=m%n
		m=n
		n=a
	} 
	fmt.Println(c/m)
}

发表于 2019-08-11 22:03:20 回复(0)
C/C++
今天打代码了吗头像 今天打代码了吗

#include<iostream>
#include<stdio.h>
using namespace std;

int gcd(int a, int b) {
    if (b == 0)return a;
    else return gcd(b, a%b);
}

int main() {
    int m, n;
    while (cin >> m >> n) {
        int c = gcd(m, n);
        cout <<(m/c)*(n/c)*c<< endl;
    }
    return 0;
}







发表于 2019-08-10 09:27:30 回复(0)
ZhiM,头像 ZhiM, 
def test(a,b):
    for i in range(1,a*b+1):
        if i % a == 0 and i % b == 0:
            print(i)
            break
test(6,2)

发表于 2019-08-08 22:06:34 回复(0)
C/C++
ePhot̶on头像 ePhot̶on 
#include <utility>

template<typename NumType>
NumType gcd(NumType a, NumType b) {
	NumType k = 0;
	while (b != 0) {
		if (b % 2 == 0) {
			if (a % 2 == 0) {
				k++;
				a /= 2; b /= 2;
			}
			else {
				b /= 2;
			}
		}
		else {
			if (a % 2 == 0) {
				a /= 2;
			}
			else {
				if (a < b) {
					std::swap(a, b);
				}
				a -= b;
			}
		}
		std::swap(a, b);
		b %= a;
	}
	return a<<k; // 等价于a*pow(2,k)
}

template<typename NumType>
NumType lcm(NumType a, NumType b) {
    return a/gcd(a,b)*b;
}

编辑于 2019-08-13 16:29:12 回复(0)
提交观点

问题信息

上传者：小小
难度：
16条回答 4651浏览

热门推荐

通过挑战的用户

相关试题

最小公倍数

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号