Project Euler #3 Java Solution Problem

Question

class eulerThree {

    public static void main(String[] args) {

     double x = 600851475143d; 

     for (double z = 2; z*z <= x; z++) {

      if (x%z == 0) {

       System.out.println(z + "PRIME FACTOR");

      }

     }

    }

}

and the output is:

71.0
839.0
1471.0
6857.0
59569.0
104441.0
486847.0

So, I assume 486847 is the largest prime factor of x, but project euler says otherwise. I don't see a problem in my code or my math, so I'm pretty confused. Can you see anything I can't?

Answer 1

double is inherently inaccurate for large values and should never be used for these type of number operations. The right class to use is BigInteger, which allows arbitrarily large integral values to be represented precisely. See this wikipedia article for a description on what floating point data types are and are not.

Answer 2

First, use BigInteger or long rather than double. Double isn't exact, and as you get to later problems, it won't be correct at all.

Second, what you're printing is factors, not prime factors.

This will work in your case:

for (double z = 2; z <= x; z++) {
        if (x%z == 0) {
     while( x%z == 0)
      x = x/z
                System.out.println(z + "PRIME FACTOR");
        }
}

Also, Project Euler gives you sample input and output. Use that, since your code doesn't output values that match the example they give in the problem.

Answer 3

Two things:

1. Don't use double, the bigger the numbers the less precision it has. Instead you can use BigInteger to store arbitrarily large integers, or in this case a simple long will suffice.

2. You need to divide by the prime factor after you find it, otherwise you'll find all factors not just prime factors. Something like this:

   if (x % z == 0) {
       System.out.println(z + "PRIME FACTOR");
       x /= z;
       z -= 1; // Might be present multiple times, try it again
   }
   

Answer 4

Firstly, you have to use an accurate arithmetic means. Others have suggested using BigInteger. You can do this. To me, it feels a bit like cheating (this will be more important for later problems that deal with much larger integers) so the more fun way (imho) is to write the necessary arbitrary precision operations yourself.

Second, 600851475143 is small enough to be done accurate with a long, which will be much faster.

Third, your loop isn't correctly checking for prime factors. You're just checking odd numbers. This is a barebones (incomplete) solution:

long num = 600851475143L;
List<Long> factors = new ArrayList<Long>(); // or use a Set
if (num & 1 == 0) {
  factors.add(2L);
}
for (long i=3; i*i<=num; i+=2) {
  // first check i is prime
  // if i is prime check if it is a factor of num
}

Checking if something is prime has differing levels of implementation. The most naive:

public boolean isPrime(long num) {
  for (long i=2; i<=num; i++) {
    if (num % i == 0) {
      return false;
    }
  }
  return true;
}

Of course that does all sorts of unnecessary checking. As you've already determined you only need to check numbers up to sqrt(n) and you can eliminate even numbers (other than 2):

public boolean isPrime(long num) {
  if (num & 1 == 0) {
    return false; // checks divisibility by 2
  }
  for (long i=3; i*i<=num; i+=2) {
    if (num % i == 0) {
      return false;
    }
  }
  return true;
}

But you can do better than this as well. Another optimization is that you only need to check a number by prime numbers within that range. The prime factors of 63 are 3 and 7. If a number isn't divisible by 3 or 7 then it by definition won't be divisible by 63.

So what you want to do is build up probably a Set<Long> or prime numbers until the square is equal to or higher than your target number. Then just check this series of numbers for divisibility into the target.