首页 > 试题广场 >

求最小公倍数

[编程题]求最小公倍数
  • 热度指数：360783 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M
  • 算法知识视频讲解
正整数A和正整数B 的最小公倍数是指 能被A和B整除的最小的正整数值，设计一个算法，求输入A和B的最小公倍数。

数据范围：

输入描述:
输入两个正整数A和B。


输出描述:
输出A和B的最小公倍数。
示例1

输入

5 7

输出

35
示例2

输入

2 4

输出

4
算法知识视频讲解
添加回答
Python
牛客57287850号头像 牛客57287850号
a,b=map(int,input().split())
l=[]
for i in range(1, min(a, b)+1):
    if a % i == 0 and b % i == 0:
        l.append(i)
print(a*b//max(l))
发表于 2021-07-11 01:19:06 回复(1)
Python
丶濑尾结弦头像 丶濑尾结弦
三行就行 
import math
a,b=map(int,input().split())
print(int(a*b/math.gcd(a, b)))


编辑于 2021-06-02 22:45:07 回复(0)
Python
FireRabbit头像 FireRabbit

为什么代码在这里运行会报错，在pycharm运行没问题，请指教！
num1=int(input(""))#赋值自变量 
num2=int(input(""))#赋值自变量
def fun(num1, num2):  # 定义一个函数,传入两个形参
    if num1 < num2:  # 判读两个整数的大小,目的为了将大的数作为除数,小的作为被除数
        num1, num2 = num2, num1  # 如果if条件满足,则进行值的交换
    product = num1 * num2  # 计算出两个整数的乘积,方便后面计算最小公倍数
    remainder= num1 % num2  # 对2个整数进行取余数
    while remainder != 0:  # 判断余数是否为0, 如果不为0,则进入循环
        num1 = num2  # 重新进行赋值,进行下次计算
        num2 = remainder
        remainder = num1 % num2  # 对重新赋值后的两个整数取余数
        # 直到 remainder等于0,得到最到公约数就退出循环
    product/= num2   # 得出最小公倍数
    print("最大公约数为:%d" % num2)    # 输出
    print("最小公倍数为:%d" % product)   # 输出
fun(num1,num2)

报错问题：
请检查是否存在语法错误或者数组越界非法访问等情况
Traceback (most recent call last):
File "/tmp/a.py3", line 11, in <module>
num1=int(input(""))#赋值自变量
ValueError: invalid literal for int() with base 10: '328 7751'

发表于 2021-04-08 16:30:16 回复(0)
Python
哈哈我么头像 哈哈我么
whileTrue:
    try:
        A,B = map(int,input().split())
        list = []
        R=A*B
        ifA == 1or B == 1:
            print(1)
        else:
            # fori in range(2,A*B+1):
                #ifi%A == 0and i%B == 0: #当A B值比较大的时候会超时,所以这个方法不行
            #     list.append(i)
            # print(min(list))
 
            fori in range(1, min(A, B)):
                ifA%i == 0and B%i==0:   #先求最大公约数，再求最小公倍数
                    list.append(i)
            print(R//max(list))
    except:
        break
发表于 2021-03-29 01:14:36 回复(0)
Python
牛客622181604号头像 牛客622181604号
import sys
 
for line in sys.stdin:
    a = line.split()
a_1 = int(a[0])
a_2 = int(a[1])   
if a_1 > a_2:
    num_1 = a_1  # num_1记录大的数
    num_2 = a_2
else:
    num_1 = a_2
    num_2 = a_1 
for i in range(2, int(num_2**0.5)+2):
    while num_1 % i == 0 and num_2 % i == 0:
        num_2 = num_2 // i
print(num_1*num_2)
发表于 2021-03-27 15:10:40 回复(0)
Python
牛客421097001号头像 牛客421097001号
百度一下最小公倍数定义，分解质因数法和公式法。
a和b的最小公倍数lcm 与最大公约数***的乘积为a*b
最大公约数可以从min（a,b）遍历至0，第一个遇到的能同时被两个数整除的就是最大公约数。同时跳出。
计算a*b/lcm即可。
最小公倍数也可以遍历，范围为max(a,b),a*b.但是程序会超时。
发表于 2021-03-17 23:02:00 回复(0)
Python
Willfu头像 Willfu 
def ggg(n, m):
    list = []
    result = 0
    for i in range(1, 10000000000):
            result = n * i
            if result % n == 0 and result % m == 0:
                list.append(result)
                break
    return min(list)



while True:
    try:
        j, k = map(int, input().split())
        print(ggg(j,k))
        
        
    except:
        break
可以参考参考 缺点是1000000000000那里，懒得改了
发表于 2021-02-27 11:41:48 回复(0)
Python
牛客512809278号头像 牛客512809278号 
num=input()
num_list=num.split()
a = eval(num_list[0])
b = eval(num_list[1])

def ab(a,b):
    i = 1
    while i%a != 0&nbs***bsp;i%b != 0:
        i += 1
    return i

print(ab(a,b))

发表于 2021-02-18 21:26:41 回复(0)
Python
榛果Haley头像 榛果Haley
python 3 解题：
思路：利用辗转相除法或者更相减损法，求出最大公约数，然后最小公倍数 = 两数相乘 / 最大公约数

def maxNum(a, b):
    if a < b:
        tmp = a
        a = b
        b = tmp
    if b == 0:
        return 0
    c = a % b
    if c == 0:
        return b
    else:
        return maxNum(b, c)

def minNum(a, b):
    c = maxNum(a, b)
    if c == 0:
        res = 0
    else:
        res = a * b / c
    return int(res)

if __name__ == "__main__":
    args = input()
    arg_list = args.split(' ')
    res = minNum(int(arg_list[0]), int(arg_list[1]))
    print(res)

发表于 2021-02-08 17:54:46 回复(0)
Python
🍃T小阿姨哟🍶头像 🍃T小阿姨哟🍶
def func1(a,b): 
    if a == 0 or b == 0:
        return False
    if a<0 and b<0:
        return False
    large = small = 0
    l = []
    if a%b == 0 or b%a == 0: 
        return max(a,b)

    if a>b:
        large = a
        small = b 

    if a<b:
        large = b 
        small = a 
        
    while large % small > 0:
        c = large % small
        num = large//small 
        l.append(num)
        large = small
        small = c 
    
    n = 1
    for i,j in enumerate(l):
        n*=j
        
    if a%n == 0 and b%n == 0:
        d = a // n   
        e = b // n   
        return n*d*e 
    else:
        
        if a%2 == 0 and b%2 == 0:
            a = a//2
            b = b//2
            return 2*a*b
        elif a%3 == 0 and b%3 == 0:
            a = a//3
            b = b//3
            return 3*a*b
        else:
            return a*b
            
           
a ,b = input().split()
a = int(a)
b = int(b)

print(func1(a,b))
发表于 2021-01-28 13:41:47 回复(0)
Python
好好运头像 好好运 
nums = input().split(" ")
if len(nums) == 2:
    int1 = int(nums[0])
    int2 = int(nums[1])
    min_ = min(int1,int2)
    for i in range(min_,int1*int2+1,min_):
        if i % int1 == 0 and i % int2 == 0:
            print(i)
            break


发表于 2021-01-17 00:36:58 回复(0)
Python
李世博头像 李世博
除去辗转相除法，还有一个小学算法：
求A与B的最小公倍数，设计如下循环：
选取A和B中较大的（如果一样大也没关系）一个数，不断乘以乘子（整数）。乘子从2开始累加。
循环不结束直到积和较小的那个数同余为0，此积为最小公倍数。

虽然也可以实现算法，但是复杂度高。 
test_list = [a,b]
bigger = int(max(test_list.split()))
multiple = 2
while (bigger*multiple) % int(min(test_list.split())) != 0:
    multiple += 1
print(bigger*multiple)


发表于 2021-01-11 19:01:40 回复(0)
Python
JeremyStar头像 JeremyStar 
def gcd(a, b):
    """Return greatest common divisor using Euclid's Algorithm."""
    while (a % b != 0):
        t = a % b
        a = b  # 新的a用原来的b值
        b = t  # 新的b用原来的余数值
    return b  # 若a除以b能整除，则b就是两个数的最大公约数。
# 首先，从键盘键入两个数a和b的值，变量t来保存余数。用while循环来判断能否整除，根据“辗转相除法”，先用第一个数a÷b再将除数b赋给a，
# 余数赋给b，循环往复，直到能整除时结束循环，此时的除数b即为最大公约数。

def lcm(a, b):
    """Return lowest common multiple."""
    return a * b // gcd(a, b)


while True:
    try:
        a, b = map(int, input().split())
        print(lcm(a, b))
    except:
        break

 特别说明：若a<b，例如a=18，b=99。t=a%b=18%99=18；新的a用原来的b值————a=99；新的b用原来的余数值b=t=18。我们发现通过一次循环交换了a、b的值，这时就能满足a>b的条件了，再继续根据辗转相除的方法即可得到最大公约数。因此，无须顾及输入的两个整数a和b谁大谁小。
编辑于 2020-12-24 12:09:50 回复(0)
Python
大溪地渔民头像 大溪地渔民 
import sys


def gcd(a, b):
    while b:
        a, b = b, a%b
    return a


def lcm(a, b):
    return a*b//gcd(a, b)


for s in sys.stdin:
    a, b = map(int, s.split())
    print(lcm(a, b))

发表于 2020-12-19 19:14:11 回复(0)
Python
天空爆炸头像 天空爆炸
大的数减去小的数得到差值，i初始化为1，判断差值乘以i是否能够整除较小的数，如果可以，则最小公倍数为较大的数乘以i 
line = raw_input()
line_split = line.split(' ')
a = int(line_split[0])
b = int(line_split[1])

large = a if a >= b else b
small = a + b - large
diff = large-small
i = 1
while True:
    if (i * diff) % small == 0:
        print i * large
        break
    else:
        i += 1


编辑于 2020-12-10 17:10:16 回复(0)
Python
牛客54046218号头像 牛客54046218号 
使用辗转相减法获得最大公约数，再用最大公约数获取商再相乘就可以 def gcd(a,b):  while a!=b:  if a>b:
            a= a-b  else:
            b=b-a  return a
A,B=map(int,input().split())
maxnum = gcd(A,B)
X = A/maxnum*B/maxnum*maxnum print(X)

发表于 2020-11-30 18:03:22 回复(0)
Python
乐观的lishan头像 乐观的lishan 
# # 2020年11月15日11:38:07
# # 解法一：暴力遍历
# # 求两个数的最小公倍数
# def Common_multiple(A, B):
# #   以两数中的最大值为步长遍历到两数相乘，求最小公倍数
# #   当两个数都较大时，算法过于耗时，其余情况下运算速度还可以
#     m = max(A, B)
#     n = min(A, B)
#     for i in range(m, A*B+1, m):
#         if i%n == 0:
#             return i

# while True:
#     try:
#         A, B = map(int, input().split())
#         num = Common_multiple(A, B)
#         print(num)
#     except:
#         break


# 解法二：辗转相除求最大公约数，利用公式求最小公倍数
# 求两个数的最大公约数数
def Common_divisor(A, B):
# 求最大公约数
    while B:
        A, B = B, A%B
    return A

while True:
    try:
        A, B = map(int, input().split())
        num = int(A*B/Common_divisor(A, B))
        print(num)
    except:
        break
                  

编辑于 2020-11-15 13:51:17 回复(0)
Python
牛客574398390号头像 牛客574398390号
input_a = int(input('请您输入A：'))
input_b = int(input('请您输入B：'))

if input_a > input_b:
    greater = input_a
else:
    greater = input_b

while True:
    if (greater % input_a == 0) and (greater % input_b == 0):
            print(greater)
            break
    else:
        greater += 1

为什么python解释器都能够通过这个却不行
发表于 2020-11-10 20:46:41 回复(0)
Python
软弱的我头像 软弱的我
python的 
while True:
    try:
        a, b = map(int, input().split())
        for i in range(1, b+1):
            if (a*i)%b == 0:
                print(a*i)
                break
    except:
        break

发表于 2020-11-08 21:56:51 回复(2)
提交观点

问题信息

基础数学 递归
难度：
58条回答 79847浏览

热门推荐

通过挑战的用户

查看代码

相关试题

求最小公倍数

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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