对于大数字,素数因子分解算法失败

Question

对于Project Euler的问题3,我遇到了一个奇怪的问题.该程序适用于其他小的数字,如13195,但当我试图处理像600851475143这样的大数字时,它会抛出此错误:

Exception in thread "main" java.lang.ArithmeticException: / by zero
    at euler3.Euler3.main(Euler3.java:16)

这是我的代码:

    //Number whose prime factors will be determined
    long num = 600851475143L;

    //Declaration of variables
    ArrayList factorsList = new ArrayList();
    ArrayList primeFactorsList = new ArrayList();

    //Generates a list of factors
    for (int i = 2; i < num; i++)
    {
        if (num % i == 0)
        {
            factorsList.add(i);
        }           
    }

    //If the integer(s) in the factorsList are divisable by any number between 1 
    //and the integer itself (non-inclusive), it gets replaced by a zero 
    for (int i = 0; i < factorsList.size(); i++)
    {
        for (int j = 2; j < (Integer) factorsList.get(i); j++)
        {
            if ((Integer) factorsList.get(i) % j == 0)
            {
                factorsList.set(i, 0);
            }
        }
    }

    //Transfers all non-zero numbers into a new list called primeFactorsList
    for (int i = 0; i < factorsList.size(); i++)
    {
        if ((Integer) factorsList.get(i) != 0)
        {
            primeFactorsList.add(factorsList.get(i));
        }
    }

为什么只有大数字导致此错误？

Answer 1

您的代码只是使用Integer,这也符合2147483647最大值这是不足为奇的用于数字比这更大时,它的失败的32位类型.请注意,您的初始循环int用作循环变量,因此如果它没有抛出异常,它将实际循环.值i将从2147483647变为-2147483648并继续.

使用BigInteger处理任意大的值,或者Long如果你满意的范围有限,但更大的一个.(long/ 的最大值Long为9223372036854775807L.)

但是,我怀疑这是否是预期的方法......这样的大数据需要很长时间.