请求排查C语言计算1到20的LCM代码错误

我看你遇到了个头疼的小问题——代码算1到10的最小公倍数完全正常，可算1到20时就出岔子，输出232792237而正确结果明明是232792560。咱们一步步拆解问题，再给出修复方案：

问题根源分析 #

你的代码出错，大概率是这几个原因导致的：

1. 整数溢出风险 #

你用int类型存储最终的LCM结果，虽然232792560本身没超过32位int的最大值（2147483647），但计算过程中中间乘积可能临时超出int范围，溢出后就会得到错误的数值。

2. 质数筛选逻辑漏洞 #

从你的代码片段来看，有两个明显的潜在问题：

• 循环范围是i=a+1到z-1，这会漏掉z本身（比如输入z=20时，20的质因数分解也需要参与LCM计算）；
• 质数判断的count变量可能没在每个数的循环前重置为0。比如第一个合数会让count变成1，之后所有质数都会因为count不为0而被错误排除，导致质数数组缺失关键质数（比如你的输出是奇数，说明完全漏掉了2这个质数）。

3. 未正确计算质数的最高次幂 #

就算质数筛选正确，如果没找到每个质数在1到z中的最高次幂（比如2的最高次幂是16=2⁴，因为2⁵=32>20），也会导致LCM计算结果偏小。

修复后的完整代码 #

下面是修正后的代码，解决了上述所有问题：

#include <stdio.h>
#include <math.h>

#define MAX 1000

int main() {
    int a, z, i, j, primes[MAX], prime_count = 0;
    // 用long long存储LCM，避免计算过程中的整数溢出
    long long lcm = 1;

    printf("Enter two numbers: ");
    scanf("%d%d", &a, &z);

    // 确保输入的a <= z，处理用户输入顺序颠倒的情况
    if (a > z) {
        int temp = a;
        a = z;
        z = temp;
    }

    // 筛选所有<=z的质数（1到z的LCM只需要考虑这些质数）
    for (i = 2; i <= z; i++) {
        int is_prime = 1;
        // 优化：质数判断只需要检查到sqrt(i)，提升效率
        for (j = 2; j <= sqrt(i); j++) {
            if (i % j == 0) {
                is_prime = 0;
                break;
            }
        }
        if (is_prime) {
            primes[prime_count++] = i;
        }
    }

    // 计算每个质数的最高次幂，并乘入LCM
    for (int k = 0; k < prime_count; k++) {
        int p = primes[k];
        long long power = p;
        // 找到最大的p^m <= z
        while (power * p <= z) {
            power *= p;
        }
        lcm *= power;
    }

    printf("LCM of %d to %d is %lld\n", a, z, lcm);

    return 0;
}

代码说明 #

• 避免溢出：用long long类型存储LCM和中间的质数幂次，确保计算过程中不会因为数值过大而溢出；
• 正确筛选质数：循环范围覆盖到z，并且每个数的质数判断前都重置is_prime标记，确保所有质数都被正确收集；
• 计算最高次幂：对每个质数，找到小于等于z的最大幂次，再乘入LCM，保证每个质数的贡献都是最大的。

运行这段代码，输入1和20，就能得到正确结果232792560了。

内容的提问来源于stack exchange，提问作者Pratik Sedhain