如何在C++中查找1000000000000这类超大数的因数？

原代码存在的核心问题 #

• 数据类型溢出：int类型的最大值约为2147483647（2^31-1），输入的1000000000000远超出该范围，会导致变量a存储溢出，后续计算全部错误。
• 内存爆炸：vector<int> f(a);试图创建包含1e12个int元素的容器，这需要约4TB内存，完全超出系统内存容量，直接导致程序崩溃。
• 效率极低：循环从1遍历到a（共1e12次），这个量级的循环在可接受时间内根本无法完成。

修正后的代码 #

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

int main() {
    long long a;
    cin >> a;
    vector<long long> factors;

    // 遍历到sqrt(a)，大幅减少循环次数
    for (long long i = 1; i <= sqrt(a); ++i) {
        if (a % i == 0) {
            factors.push_back(i);
            // 避免完全平方数重复添加相同因数
            if (i != a / i) {
                factors.push_back(a / i);
            }
        }
    }

    // 输出所有因数（如需排序可添加sort(factors.begin(), factors.end())）
    for (long long factor : factors) {
        cout << factor << "\n";
    }

    return 0;
}

关键修改说明 #

1. 数据类型替换：将int改为long long，确保能存储1e12这类超大数值，避免溢出。
2. 动态内存管理：不再预先分配vector空间，改用push_back动态添加因数，彻底解决内存不足问题。
3. 循环效率优化：遍历范围缩小到sqrt(a)，循环次数从1e12降至1e6，程序运行时间从“不可完成”变为毫秒级。
4. 去重处理：针对完全平方数，避免重复添加相同的因数（如100的因数10，只添加一次）。

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