I have run into a weird issue for prob开发者_如何学Pythonlem 3 of Project Euler. The program works for other numbers that are small, like 13195, but it throws this error when I try to crunch a big number like 600851475143:

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

Here's my code:

    //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));
        }
    }

Why is it only big numbers that cause this error?

Your code is just using Integer, which is a 32-bit type with a maximum value of 2147483647. It's unsurprising that it's failing when used for numbers much bigger than that. Note that your initial loop uses int as the loop variable, so would actually loop forever if it didn't throw an exception. The value of i will go from the 2147483647 to -2147483648 and continue.

Use BigInteger to handle arbitrarily large values, or Long if you're happy with a limited range but a larger one. (The maximum value of long / Long is 9223372036854775807L.)

However, I doubt that this is really the approach that's expected... it's going to take a long time for big numbers like that.

Not sure if it's the case as I don't know which line is which - but I notice your first loop uses an int.

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

As num is a long, its possible that num > Integer.MAX_INT and your loop is wrapping around to negative at MAX_INT then looping until 0, giving you a num % 0 operation.

Why does your solution not work?

Well numbers are discrete in hardware. Discrete means thy have a min and max values. Java uses two's complement, to store negative values, so 2147483647+1 == -2147483648. This is because for type int, max value is 2147483647. And doing this is called overflow.

It seems as if you have an overflow bug. Iterable value i first becomes negative, and eventually 0, thus you get java.lang.ArithmeticException: / by zero. If your computer can loop 10 million statements a second, this would take 1h 10min to reproduce, so I leave it as assumption an not a proof.

This is also reason trivially simple statements like a+b can produce bugs.

How to fix it?

package margusmartseppcode.From_1_to_9;

public class Problem_3 {
    static long lpf(long nr) {
        long max = 0;

        for (long i = 2; i <= nr / i; i++)
            while (nr % i == 0) {
                max = i;
                nr = nr / i;
            }

        return nr > 1 ? nr : max;
    }

    public static void main(String[] args) {
        System.out.println(lpf(600851475143L));
    }
}

You might think: "So how does this work?"

Well my tough process went like:

1. (Dynamical programming approach) If i had list of primes x {2,3,5,7,11,13,17, ...} up to value x_i > nr / 2, then finding largest prime factor is trivial:
   • I start from the largest prime, and start testing if devision reminder with my number is zero, if it is, then that is the answer.
   • If after looping all the elements, I did not find my answer, my number must be a prime itself.
2. (Brute force, with filters) I assumed, that
   • my numbers largest prime factor is small (under 10 million).
   • if my numbers is a multiple of some number, then I can reduce loop size by that multiple.

I used the second approach here.

Note however, that if my number would be just little off and one of {600851475013, 600851475053, 600851475067, 600851475149, 600851475151}, then my approach assumptions would fail and program would take ridiculously long time to run. If computer could execute 10m statements per second it would take 6.954 days, to find the right answer.

In your brute force approach, just generating a list of factors would take longer - assuming you do not run out of memory before.

Is there a better way?

Sure, in Mathematica you could write it as:

P3[x_] := FactorInteger[x][[-1, 1]]
P3[600851475143]

or just FactorInteger[600851475143], and lookup the largest value.

This works because in Mathematica you have arbitrary size integers. Java also has arbitrary size integer class called BigInteger.

Apart from the BigInteger problem mentioned by Jon Skeet, note the following:

1. you only need to test factors up to sqrt(num)
2. each time you find a factor, divide num by that factor, and then test that factor again
3. there's really no need to use a collection to store the primes in advance

My solution (which was originally written in Perl) would look something like this in Java:

long n = 600851475143L;          // the original input
long s = (long)Math.sqrt(n);     // no need to test numbers larger than this
long f = 2;                      // the smallest factor to test
do {
    if (n % f == 0) {            // check we have a factor
         n /= f;                 // this is our new number to test
         s = (long)Math.sqrt(n); // and our range is smaller again
    } else {                     // find next possible divisor
         f = (f == 2) ? 3 : f + 2;
    }
} while (f < s);                 // required result is in "n"