Project Euler - Problem 3

Time for another one! I'm getting through these faster than I would've thought!

This one took me a bit more time simply because I made some stupid mistakes, mainly forgetting operation precedence and leaving out a set of brackets. I probably should start commenting my code and learn to use the debugging tools in Eclipse.

Problem 3
The prime factors of 13195 are 5, 7, 13 and 29.

What is the largest prime factor of the number 600851475143 ?

After considering my approach for five minutes or so I've decided that the best way to tackle this will be to work backwards starting from half of the number (the largest possible factor. In this case it won't be one because the number is odd but I want a general solution), checking each number to first establish if it is a factor and then whether it is prime or not. The first number found matching both conditions is the answer.

Of course, that isn't even close to what I ended up on. I tried that method (I won't post the code, no need) and it was ridiculously slow. The method I came up with after experimenting a bit works much more efficiently.

In the end I used a for loop incrementing i from 2 and dividing the number by i to work out the highest factor, second highest factor, etc, and then checking each of those for candidacy which seemed to work quite well and calculated well under the 60 second limit suggested by ProjectEuler.

Here is my source:

public class Problem3 {

 static final long PROBLEMNUMBER = 600851475143l;

 public static void main(String[] args){
  for(long i = 2; i < PROBLEMNUMBER / 2; i++){
   if(PROBLEMNUMBER % i == 0){
    System.out.println(PROBLEMNUMBER/i);
    if(isPrime(PROBLEMNUMBER/i)){
     System.out.println("Answer: " + PROBLEMNUMBER/i + ", " + i);
     break;
    }
   }
  }

 }

 public static boolean isPrime(long theNumber){
  long limit = (long) Math.sqrt(theNumber) + 1l;
  for(long i = 2; i < limit; i++){
   if(theNumber % i == 0){
    return false;
   }
  }
  return true;
 }



}

It's not *perfect* code, but I'm reasonably happy with the efficiency, especially compared to my old solution. A friend tells me I could use hash tables somehow to increase the efficiency of my prime checking function but I don't really understand how that works... Might have to do a bit of research.

Enough of this now though. This solution gave me the right answer according to ProjectEuler so I'm happy.
Now, time to go. I've got some bonsai to read about.