首页 > 试题广场 >

求最小公倍数

[编程题]求最小公倍数
  • 热度指数：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 3
Sigma4头像 Sigma4 
# 哭辽，不知道辗转相除法在那一直打转，真是拉胯呀，搞了好几个小时😭，期间模拟了几组数据发现最小公倍数=两者积/最大公约数，然后真给猜对了哈哈（题目标签是简单，所以愣是想着拒绝看题解或讨论或百度，务必要自己试着做出来）

import sys
import math

def rec(n, count):
    if n % 2 != 0:
        return (count, n)
    else:
        count +=1
        return rec(n>>1,count)

def rec2(n1, n2, d):
    # if d > max(n1, n2):return 0   
    # 这里会超过递归的层数限制(1000左右)，所以换一种思路：
    # 如果两个数能被某个小公约数整除，只需要参考更小的那个数
    # 然而对于这个数来说，小公约数不可能超过这个数的平方根
    if d > int(math.sqrt(min(n1, n2))) + 1:return 0
    if n1 % d == 0 and n2 % d ==0:
        return d
    else:
        return rec2(n1, n2, d+2)

def rec3(n, o, count):
    if n % o != 0:
        return count
    else:
        count +=1
        return rec3(n/o, o, count)

for line in sys.stdin:
    a = line.split()
    # print(a)
    max_ = max(int(a[0]), int(a[1]))
    min_ = min(int(a[0]), int(a[1]))
    if max_ % min_ == 0:
        print(max_)
    elif max_ % 2 ==0 and min_ % 2 == 0: # 8 12
        max_c = rec(max_, 0)[0]
        min_c = rec(min_, 0)[0]
        print(int(max_ * min_ / (2 ** min(max_c, min_c))))
    else: # 27 45/36
        min_div = rec2(max_, min_, 3)
        if min_div == 0:
            print(max_ * min_)
        else:
            max_c = rec3(max_, min_div, 0)
            min_c = rec3(min_, min_div, 0)
            print(int(max_ * min_ / (min_div ** min(max_c, min_c))))
    # else: # 27 12
    #     if max_ % 2 ==0:
    #         factor = rec(max_, 0)[1]

发表于 2024-07-12 23:13:11 回复(0)
Python 3
无我无他头像 无我无他
a,b = map(int,input().split())
if a>b:
    a,b = b,a
if b%a==0:
    print(b)
else:
    for i in range(a-1,0,-1):
        if a%i==0 and b%i==0:
            print(int(a*b/i))
            break
发表于 2024-01-30 19:04:08 回复(0)
Python 3
三水灬头像 三水灬
import sys

for line in sys.stdin:
    a = line.strip().split()
    nums1 = int(a[0])
    nums2 = int(a[1])
    start = max(nums1,nums2)
    end = nums1*nums2
    for i in range(start,end+1,start):
        if i%nums1 == 0 and i%nums2 == 0:
            print(i)
            break

编辑于 2023-12-08 22:17:50 回复(0)
Python 3
同桌在刷题头像 同桌在刷题
提交不了。。。 
a, b = map(int, input().split())
c = a if a > b else b
if c % a == 0 and c % b == 0:
    print(c)
else:
    print(a * b)




发表于 2023-05-30 23:05:01 回复(0)
Python 3
立志实干头像 立志实干 
def main():

    a = input("")
    b = len(a)

    c = 0
    while c < b - 1:

        if a[c] == " ":
            break
        c += 1

    d = 0
    e = ""
    while d < c:
        e += a[d]
        d += 1

    f = c + 1
    g = ""
    while f < len(a):
        g += a[f]
        f += 1

    e = int(e)
    g = int(g)

    h = min(e, g)
    j = max(e, g)

    k = 2
    while k <= h:
        if h % k == 0 and j % k == 0:
            h = h / k
            if h % k != 0:
                k += 1
        else:
            k += 1
    t = int(h * j)
    print(t)


main()

发表于 2023-04-10 20:48:54 回复(0)
Python 3
牛客670426696号头像 牛客670426696号
x=list(input().split())
A=int(x[0])
B=int(x[1])
Max=0
Min=0
N=1
D=A*B
if A>B:
    Max=A
    Min=B
else:
    Max=B
    Min=A
#print(Max,Min,D)
for x in range(Max,D+1,Max):
    if x%Min==0:
        print(x)
        break

发表于 2023-03-12 10:18:31 回复(0)
Python 3
布娃娃君君头像 布娃娃君君
while True:
    try:
        A,B=list(map(int,input().strip().split(' ')))
        mi=min(A,B)
        yue=1
        for i in range(1,mi+1):
            if (A%i==0) and (B%i==0):
                yue=i
        bei=A*B//yue
        print(bei)
    except:
        break
发表于 2022-12-27 15:16:02 回复(0)
Python 3
在喝茶的咸鱼很温柔头像 在喝茶的咸鱼很温柔 
str_n=input()
x=int(str_n.split(' ')[0])
y=int(str_n.split(' ')[1])
if x<y:
    x,y=y,x
for i in range(x,x*y+1,x):
    if i%y==0:
        print(i)
        break

发表于 2022-12-24 16:58:43 回复(0)
Python 3
肆歌头像 肆歌
a = input()
n, m = int(a.split()[0]), int(a.split()[1])
ls = [i for i in range(1,10) if n % i == 0 and m % i == 0]
print(int(m*n/max(ls)))
发表于 2022-09-14 16:44:48 回复(0)
Python 3
牛客527980301号头像 牛客527980301号
def f(a,b):
    if a > b:
        a,b = b,a
    for i in range(a,0,-1):
        if a % i == 0 and b % i == 0:
            return i
            break
while True:
    try:
        x,y = map(int,input().split())
        print(int(x*y/f(x,y)))
    except:
        break
发表于 2022-09-04 16:17:35 回复(0)
Python 3
Loverchoo头像 Loverchoo
a,b=list(map(int,input().split()))
for i in range(max(a,b),a*b+1,max(a,b)):
    if i%min(a,b)==0:
        print(i)
        break
    
发表于 2022-08-31 02:47:23 回复(0)
Python 3
牛客428544446号头像 牛客428544446号
A, B = map(int, input().split())
n = 1
if B%A==0 or A%B==0:
    print(max(A,B))
else:
    for i in range(2,min(A,B)+1):
        while A%i==0 and B%i==0:
            n=n*i
            A=A//i
            B=B//i
    print(n*A*B)
发表于 2022-08-27 22:04:11 回复(0)
Python 3
麓南的风头像 麓南的风 
#直接挨个遍历容易超时，那就减少遍历次数
#从最小的输入值开始遍历，步长为最小输入值
while True:
    try:
        n,m = map(int,input().split())
        for i in range(min(n,m),n*m + 1,min(n,m)):
            if i % n == 0 and i % m == 0:
                print(i)
                break
    except:
        break
减少遍历次数，勉强不超时
发表于 2022-08-22 00:14:26 回复(0)
Python 3
进击的皮皮举头像 进击的皮皮举 
a,b=map(int,input().split())
n=a*b 
c=min(a,b)
d=max(a,b)
for x in range(2,c+1):
    if a%x==0 and b%x==0 :
        break
if x==c:
    print(n)
elif d%c==0:
    print(d)
else:
    print(int(n/x))

发表于 2022-08-14 17:02:46 回复(0)
Python 3
牛客179825537号头像 牛客179825537号
# 1、如果两个数是互质数，那么它们的最小公倍数就是这两个数的乘积。
#
# 2、如果两个数有倍数关系，那么较大的数就是这两个数的最小公倍数。
#
# 3、如果两数不是互质，也没有倍数关系时，可以把较大数依次扩大2倍、3倍、……看扩大到哪个数时最先成为较小数的倍数时，这个数就是这两个数的最小公倍数。
def zs(n): # 先定义一个判断是否为质数的函数
    for i in range(2,n):
        while n % i == 0:
            return False
    else:
        return True
while True:
    try:
        n = input().split()
        s = list(n)
        if max(int(s[0]),int(s[1])) % min(int(s[0]),int(s[1])) == 0: # 判断是否有倍数关系，有倍数关系则较大的数为公倍数
            print(max(int(s[0]),int(s[1])))
        elif zs(int(s[0])) is True and zs(int(s[1])) is True: # 判断是否互为质数，互为质数则公倍数是两个数的乘积
            print(int(s[0])*int(s[1]))
        else:
            for i in range(2,10000):
                if max(int(s[0]),int(s[1]))*i % min(int(s[0]),int(s[1])) == 0: # 将较大的数从2开始乘，直到变成较小的数的倍数时，则为最小公倍数
                    print(max(int(s[0]),int(s[1]))*i)
                    break
    except:
        break
发表于 2022-08-06 17:35:01 回复(1)
Python 3
Justinshadow头像 Justinshadow 
#用递归方式模拟短除法
def back(num1:int,num2:int,res=1):
    m = min(num1,num2)
    if num1%num2 == 0&nbs***bsp;num2%num1==0:
        return max(num1,num2)
    else:
        for i in range(2,m+1):
            if num1%i==0 and num2%i==0:
                return back(num1//i,num2//i,res*i)
    return num1*num2*res

a,b = map(int,input().split())
print(back(a,b))

发表于 2022-07-29 15:16:16 回复(0)
Python 3
649924619头像 649924619
c = input().split()
a = int(c[0])
b = int(c[1])
for i in range(1,b+1):
    if a*i%b == 0:
        print(a*i)
        break
        

发表于 2022-07-24 14:34:15 回复(0)
提交观点

问题信息

基础数学 递归
难度：
74条回答 79846浏览

热门推荐

通过挑战的用户

查看代码

相关试题

求最小公倍数

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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