Euler Problem 3

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

Euler Problem 3

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

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s