素因式分解

Question

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

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

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

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

它对小的数字很好，但是当我输入一个大的数字，像809800987876，我得到一个-1后，大约3个因素。

这是809800987876的样本输出。

> 2 2 486957767
> -1

我怎么才能解决这个问题？

Answer 1

你的int满溢了。在典型系统中，int的最大值为2147483647。809800987876比那个大，所以它就溢出了。您可以使用long long，它的最大值至少为9223372036854775807。