@[华为算法题](正整数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())