如何用C++计算最多30个最大10^6的数的LCM（结果超long long）

要处理结果达10^50的LCM计算，核心思路是质因数分解+大整数乘法，避免直接计算过程中溢出。

步骤1：质因数分解所有输入数 #

LCM的本质是各质因数最高次幂的乘积，所以先对每个输入数分解质因数，记录每个质数的最大指数：

1. 先用埃氏筛预处理10^6以内的所有质数，方便快速分解。
2. 对每个输入数，用质数试除，统计每个质因数的指数，更新全局的最大指数记录。

代码示例：

#include <vector>
#include <iostream>
using namespace std;

// 埃氏筛生成1e6以内的质数
vector<int> sieve(int max_n) {
    vector<bool> is_prime(max_n + 1, true);
    is_prime[0] = is_prime[1] = false;
    for (int i = 2; i * i <= max_n; ++i) {
        if (is_prime[i]) {
            for (int j = i * i; j <= max_n; j += i) {
                is_prime[j] = false;
            }
        }
    }
    vector<int> primes;
    for (int i = 2; i <= max_n; ++i) {
        if (is_prime[i]) primes.push_back(i);
    }
    return primes;
}

vector<int> max_exponents(1000001, 0); // 存储每个质数的最大指数

// 分解单个数字的质因数，更新最大指数
void factorize(int n, const vector<int>& primes) {
    for (int p : primes) {
        if ((long long)p * p > n) break;
        if (n % p == 0) {
            int cnt = 0;
            while (n % p == 0) {
                cnt++;
                n /= p;
            }
            if (cnt > max_exponents[p]) {
                max_exponents[p] = cnt;
            }
        }
    }
    if (n > 1) { // 剩余的数本身是质数
        if (1 > max_exponents[n]) {
            max_exponents[n] = 1;
        }
    }
}

步骤2：实现大整数乘法 #

用数组存储大整数的每一位（低位在前），实现乘法逻辑，避免溢出：

// 大整数乘法：num（低位在前）乘以x，返回结果
vector<int> multiply(vector<int> num, int x) {
    int carry = 0;
    for (size_t i = 0; i < num.size(); ++i) {
        long long product = (long long)num[i] * x + carry;
        num[i] = product % 10;
        carry = product / 10;
    }
    while (carry > 0) {
        num.push_back(carry % 10);
        carry /= 10;
    }
    return num;
}

步骤3：计算最终LCM #

遍历所有质数，将其最大次幂乘入大整数中，最后输出结果：

int main() {
    // 示例输入：可替换为你的30个数字
    vector<int> nums = {12, 18, 24, 36, 48, 60, 72, 84, 96, 108};
    vector<int> primes = sieve(1000000);

    // 分解所有输入数的质因数
    for (int n : nums) {
        factorize(n, primes);
    }

    // 初始化LCM为1（低位在前）
    vector<int> lcm = {1};
    for (int p : primes) {
        if (max_exponents[p] == 0) continue;
        // 乘以p的max_exponents[p]次方
        for (int i = 0; i < max_exponents[p]; ++i) {
            lcm = multiply(lcm, p);
        }
    }

    // 输出结果（从高位到低位）
    cout << "LCM结果：";
    for (auto it = lcm.rbegin(); it != lcm.rend(); ++it) {
        cout << *it;
    }
    cout << endl;

    return 0;
}

补充说明 #

• 埃氏筛预处理10^6以内的质数，时间开销极小，完全适配你的输入规模。
• 大整数乘法逻辑简单，针对10^50级别的结果，数组存储的长度最多51位，计算效率足够。
• 如果追求更高效率，可以优化为先计算质数的幂（在long long范围内的话）再乘入大整数，避免多次循环，但直接循环乘质数的方式更稳妥，无需额外判断。

内容的提问来源于stack exchange，提问作者Anh Trí Hoàng