基于Counter实现LCM函数的问题：如何取质因数最高计数并计算LCM

问题核心 #

你当前用Counter(prime_factors(a) + prime_factors(b))的方式，本质是把两个数的质因数出现次数相加，但LCM要求的是每个质因数在两个数中的最高次幂，所以必须调整Counter的合并逻辑。

替换+的正确写法 #

不能再用列表相加后转Counter的思路，应该分别为两个数生成独立的Counter，再合并时保留每个质因数的最大计数：

• 若使用Python 3.10及以上版本，直接用Counter的|运算符（取并集，自动保留每个键的最大计数），这是最简洁的写法。
• 兼容旧版本Python的话，手动遍历所有质因数，取两个Counter中的最大值。

先处理Counter再计算LCM的实现 #

完全可以先处理好Counter再计算最终LCM，以下是具体代码示例：

示例1（Python 3.10+ 简洁版）

from collections import Counter

def prime_factors(n):
    # 质因数分解函数，返回质因数列表
    factors = []
    while n % 2 == 0:
        factors.append(2)
        n = n // 2
    i = 3
    while i * i <= n:
        while n % i == 0:
            factors.append(i)
            n = n // i
        i += 2
    if n > 2:
        factors.append(n)
    return factors

def lcm(a, b):
    # 分别生成两个数的质因数Counter
    cnt_a = Counter(prime_factors(a))
    cnt_b = Counter(prime_factors(b))
    # 合并Counter，取每个质因数的最高次幂
    max_exponents = cnt_a | cnt_b
    # 计算LCM：所有质因数的（底数^最高次幂）相乘
    lcm_value = 1
    for prime, exp in max_exponents.items():
        lcm_value *= prime ** exp
    return lcm_value

# 测试：200和10的LCM应为200
print(lcm(200, 10))  # 输出200

示例2（兼容Python 3.9及以下版本）

from collections import Counter

def prime_factors(n):
    factors = []
    while n % 2 == 0:
        factors.append(2)
        n = n // 2
    i = 3
    while i * i <= n:
        while n % i == 0:
            factors.append(i)
            n = n // i
        i += 2
    if n > 2:
        factors.append(n)
    return factors

def lcm(a, b):
    cnt_a = Counter(prime_factors(a))
    cnt_b = Counter(prime_factors(b))
    # 收集所有出现过的质因数
    all_primes = set(cnt_a.keys()).union(cnt_b.keys())
    max_exponents = {}
    # 遍历每个质因数，取两个数中的最高次幂
    for p in all_primes:
        max_exponents[p] = max(cnt_a.get(p, 0), cnt_b.get(p, 0))
    # 计算LCM
    lcm_value = 1
    for prime, exp in max_exponents.items():
        lcm_value *= prime ** exp
    return lcm_value

# 测试
print(lcm(200, 10))  # 输出200

关键逻辑说明 #

• 先分别生成cnt_a和cnt_b：各自统计对应数字的质因数出现次数。
• 合并时取每个质因数的最大次数：这符合LCM的数学定义——LCM(a,b)是所有质因数的最高次幂的乘积。
• 最后遍历合并后的Counter，计算乘积得到LCM。

内容的提问来源于stack exchange，提问作者John Phillip