This was the 1st problem that caused me a little bit of thinking time, and hence the idea to blog.

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

What is the largest prime factor of the number 600851475143 ?

**Solution / Thoughts**

My 1st thought which I knew would clearly take far too long was to loop from i = 3 to 600851475143. This posed 2 problems – (a) looping for that long would take forever, and also (b) the largest prime factor was likely to be found long before the large number involved. Another thought was to loop backwards, but again this wouldn’t overcome reason (b).

The loop was speeded up slightly by incrementing by 2 rather than the traditional 1 in a for…loop, but that really didn’t do anything to overcome the problems already identified.

My way of solving it still relied on the loop thought, but worked with the idea of finding the correlating value for the earlier successful divisions. So my final implementation was:

long number = 600851475143L;

for (long i = 3; i < number; i = i + 2) {

if ((number % i) == 0) {

long temp = number / i;

if (isPrime(temp)) {

System.out.println(temp);

break;

}

}

}

* There are plenty of isPrime() sample methods available on the Internet.

Answer: 6857