首页 > 试题广场 >

求最小公倍数

[编程题]求最小公倍数

热度指数：369265 时间限制：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

输出

算法知识视频讲解

Python 3

我什么时候找到工作

遍历法
1、最小公倍数（Least Common Multiple, LCM）是指能够同时被两个整数 a 和 b 整除的最小的正整数；即 a * k1 = b * k2 = c，其中 c 为最小公倍数，k1 和 k2 是正整数。
2、遍历可能的公倍数：[b, ab] 且步长为 b 的数列中，判断当前数 nb 是否可以被 a 整除，返回第一个被整除的值。注意 a <= b，这样可以加快搜索。

a, b = map(int, input().split(' '))  # a、b是正整数

if a > b:
    a, b = b, a

for i in range(b, a * b + 1, b):
    if i % a == 0:
        print(i)
        break

数学公式法：若有最大公倍数 g = gcd(a, b), 则最小公倍数的公式为 lcm = abs(a * b) / g

def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a % b)

a, b = map(int, input().split(' '))  # a、b是正整数
lcm = (a * b) // gcd(a, b)
print(lcm)

发表于 2025-06-22 16:29:46 回复(0)

Python 3

牛客482602990号

import math

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

print(int(a*b/math.gcd(a,b)))

发表于 2025-04-20 12:25:18 回复(0)

Python 3

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号

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号

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

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号

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号

# 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

#用递归方式模拟短除法
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)