最小公倍数算法题题解
程序员文章站
2023-11-19 18:09:40
@[华为算法题](正整数A和正整数B 的最小公倍数是指 能被A和B整除的最小的正整数值,设计一个算法,求输入A和B的最小公倍数。)python实现这是按照我个人思路实现的。import datetimedef get_com_val(): a = int(input("请输入a:")) b = int(input("请输入b:")) begin_time = datetime.datetime.now() if a>b: n_min = b...
@[华为算法题](正整数A和正整数B 的最小公倍数是指 能被A和B整除的最小的正整数值,设计一个算法,求输入A和B的最小公倍数。)
python实现
这是按照我个人思路实现的。
实现一:
import datetime
def get_com_val():
a = int(input("请输入a:"))
b = int(input("请输入b:"))
begin_time = datetime.datetime.now()
if a>b:
n_min = b
n_max = a
else:
n_min = a
n_max = b
if n_max%n_min == 0:
return n_max
dict = {}
for i in range(2, n_max):
if i > n_max:
break
if n_max % i == 0:
cout = 0
while n_max % i == 0:
n_max = int(n_max/i)
cout += 1
if i in dict.keys():
if dict[i] < cout:
dict[i] = cout
else:
dict[i] = cout
if n_min % i == 0:
cout = 0
while n_min % i == 0:
n_min = int(n_min/i)
cout += 1
if i in dict.keys():
if dict[i] < cout:
dict[i] = cout
else:
dict[i] = cout
val = n_min * n_max
for key, k_val in dict.items():
val *= key**k_val
end_time = datetime.datetime.now()
d_time = end_time - begin_time
print("运行时间:%f" % d_time.total_seconds())
return val
if __name__ == '__main__':
print("当前最小公倍数:{}".format(get_com_val()))
实现二:
def m_split(num):
dict = {}
i = 1
while num > i:
i += 1
if num % i == 0:
count = 0
while num % i == 0:
num = int(num / i)
count += 1
dict[i] = count
else:
dict[num] = 1
return dict
def get_com_val():
n = input().split()
a = int(n[0])
b = int(n[1])
mul = a * b
a_dict = m_split(a)
b_dict = m_split(b)
c_dict = {}
for a_k, a_v in a_dict.items():
if a_k in b_dict.keys():
if a_v < b_dict[a_k]:
c_dict[a_k] = a_dict[a_k]
else:
c_dict[a_k] = b_dict[a_k]
m_v = 1
for k, k_v in c_dict.items():
m_v *= k ** k_v
return int(mul / m_v)
print(get_com_val())
实现三:
import datetime
def get_com_val():
n = input().split()
a = int(n[0])
b = int(n[1])
dict = {}
for i in range(2, a):
if a % i == 0:
cout = 0
while a % i == 0:
a = int(a/i)
cout += 1
if i in dict.keys():
if dict[i] < cout:
dict[i] = cout
else:
dict[i] = cout
if b % i == 0:
cout = 0
while b % i == 0:
b = int(b/i)
cout += 1
if i in dict.keys():
if dict[i] < cout:
dict[i] = cout
else:
dict[i] = cout
val = a * b
for key, k_val in dict.items():
val *= key**k_val
return val
print(get_com_val())
本文地址:https://blog.csdn.net/weixin_41964616/article/details/107125343