质因数分解

Question

我这里有一个简单的因式分解算法。

void primeFactor(int number){
    if (number == 1)return;

    int x = 2;
    while (number%x != 0)x++;

    cout << x << endl;
    primeFactor(number / x);
}

它适用于小数字，但每当我输入一个大数字（如 809800987876）时，我在大约 3 个因子后得到 -1。

这是 809800987876 的示例输出。

> 2 2 486957767
> -1

我该如何解决这个问题？

Answer 1

您溢出 int。在典型系统上，int 的最大值为 2147483647。809800987876 大于该值，因此会溢出。您可以使用 long long，它的最大值至少为 9223372036854775807。

质因数分解

Prime factorization

c++

prime-factoring