为何我的C++代码处理超大整数时崩溃？（Project Euler第3题）

你的代码出现段错误和算术异常，核心原因集中在以下几点：

1. 整数类型溢出 #

int的常规取值范围是**-2147483648 到 2147483647**（约20亿），而你设置的number = 22143223844远超这个范围，直接用int存储会触发溢出，导致算术异常和未定义行为。

2. 栈数组越界 #

你在栈上声明了int Primes[size];，栈内存空间有限，一旦cur_ind超过10000，就会越界写入栈内存，破坏栈结构，引发段错误。

3. 函数命名混淆 #

is_coprime函数名意为“互质”，但实际实现的是判断大数不能被小数整除，虽然功能适配当前需求，但命名容易误导，增加调试难度。

修复后的代码 #

替换整数类型为long long避免溢出，用vector<int>动态存储质数防止越界，同时修正函数命名：

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// 判断value是否能被divisor整除
bool is_divisible(long long value, int divisor)
{
    return (value % divisor == 0);
}

int find_next_prime(vector<int>& primes)
{
    int k;
    if (primes.empty()) {
        k = 1;
    } else {
        k = primes.back() - 1;
    }

    while (true) {
        k++;
        bool is_prime = true;
        for (int p : primes) {
            if (is_divisible(k, p)) {
                is_prime = false;
                break;
            }
        }
        if (is_prime) {
            return k;
        }
    }
}

int reducer(vector<int>& primes, long long value)
{
    // 先检查已有的质数
    for (int p : primes) {
        if (is_divisible(value, p)) {
            return p;
        }
    }

    // 生成新质数直到找到能整除的
    while (true) {
        int next_p = find_next_prime(primes);
        primes.push_back(next_p);
        if (is_divisible(value, next_p)) {
            return next_p;
        }
    }
}

int main()
{
    vector<int> primes;
    long long number = 22143223844LL;
    int max_prime = 0;
    int cur_prime;

    while (number != 1) {
        cur_prime = reducer(primes, number);
        max_prime = max(max_prime, cur_prime);
        number /= cur_prime;
        cout << ".. " << cur_prime << endl;
    }

    cout << "最大质因数是: " << max_prime << endl;
    return 0;
}

额外优化建议 #

• 找下一个质数时，只需检查到sqrt(k)即可，不用遍历所有已存质数，能大幅提升效率（若k有大于√k的因数，对应的另一个因数必然小于√k）。
• 针对Project Euler第3题，无需生成所有质数，直接从2开始试除，每次找到能整除的因数就将number除以它，直到number变为1，最后一个因数就是最大质因数，这种方法更高效。

内容的提问来源于stack exchange，提问作者E-wokker