使用埃拉托斯特尼筛法做质因数分解时出现Floating point exception问题求助

嘿，我来帮你排查这个问题！你遇到的"Floating point exception (core dumped)"其实不是真的浮点运算错误，大多是因为整数除以0或者数组越界导致的，咱们一步步拆解你的代码问题：

主要错误点分析 #

• 除以0的致命问题：当输入的n是质数时，你的筛法数组arr[n]会保持初始值0，这时候执行n = n / arr[n]就相当于除以0，直接触发异常。另外，即使n不是质数，分解到最后一步时，arr[n]也可能为0，同样会出问题。
• 变长数组不兼容C++标准：int primeFactors[n]属于变长数组（VLA），这是C99的特性，C++标准并不支持，不同编译器表现可能不一致，容易引发内存问题。
• 输出循环逻辑错误：最后输出的循环条件是i < n，但前面的分解循环已经把n修改到1了，这个循环根本不会执行，你永远看不到结果。
• 固定大小数组的越界风险：int arr[100]的大小是固定的，如果输入的n大于100，筛法过程中访问arr[k]就会超出数组范围，导致未定义行为。

修正后的代码 #

我把这些问题都修复了，同时优化了筛法和分解逻辑：

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

void primeFactor(int n) {
    // 用vector代替固定数组，避免越界，大小设为n+1覆盖所有可能的索引
    vector<int> arr(n + 1, 0);
    // 埃拉托斯特尼筛法优化：i遍历到sqrt(n)即可，同时处理每个质数的倍数从2*i开始（避免i*i过大溢出）
    for (int i = 2; i * i <= n; ++i) {
        if (arr[i] == 0) {
            for (int k = 2 * i; k <= n; k += i) {
                // 只记录最小的质因数，这样分解时能正确回溯
                if (arr[k] == 0) {
                    arr[k] = i;
                }
            }
        }
    }

    vector<int> primeFactors;
    int temp = n; // 用临时变量保存原始n，避免修改后影响后续逻辑
    while (temp > 1) {
        if (arr[temp] == 0) {
            // 说明temp本身是质数
            primeFactors.push_back(temp);
            break;
        }
        primeFactors.push_back(arr[temp]);
        temp /= arr[temp];
    }

    // 输出所有质因数
    for (size_t i = 0; i < primeFactors.size(); ++i) {
        if (i > 0) {
            cout << " * "; // 加个分隔符更清晰
        }
        cout << primeFactors[i];
    }
    cout << endl;
}

int main(int argc, char const *argv[]) {
    int n;
    cout << "请输入要分解的数字：";
    cin >> n;
    if (n < 2) {
        cout << "请输入大于等于2的整数！" << endl;
        return 1;
    }
    primeFactor(n);
    return 0;
}

关键优化说明 #

• 用vector替代固定大小数组和变长数组，保证内存安全且符合C++标准。
• 筛法中只记录每个数的最小质因数，分解时能高效回溯。
• 分解过程用临时变量temp保存原始输入，避免修改n导致逻辑混乱。
• 增加了输入合法性检查，处理n<2的情况。
• 输出时添加分隔符，让结果更易读。

内容的提问来源于stack exchange，提问作者everyone everywhere