Project Euler: Problem 3

Problem 3 in Project Euler is as follows:

The prime factors of 13195 are 5, 7, 13 and 29.
What is the largest prime factor of the number 600851475143 ?

I noticed some performance issues with Groovy when I was working on this solution. I will blog about my findings later (Update: see here), suffice to say I am switching to straight Java for this solution.

After experimenting with a brute force approach, I finally came up with this solution. It is not the most elegant, but it works (in <100ms).

long x = 600851475143L; 
long max = x / 2;
long factor = x;
long lastFactor = x;
for (long i=2; i= lastFactor-1) {
		for (long j=factor; j>2; j--) {
			i++;
			remainder = x % j;
			if (remainder == 0) {
				if (eule3.isPrime(j)) {
					printAndExit(j);
				}			
			}
		}
	}
}

There are 2 main parts to the solution. The first loop starts at x/2 (since no factor of x can be greater than x/2). Basically we are checking if x/2 (rounded) is a factor of x. Then 3, then 4 etc. And when we find a number that is a factor, we check if it is prime (if so, we stop obviously). So, for example, we check if 50, 33, 25 are factors of x.

This approach works great, until a certain point, which is when we switch into the second loop. Basically, it becomes more inefficient to start checking if sequential numbers are factors of x.

Again, not the most efficient algorithm, or very well explained! But I have spent enough time on this one.

On to Problem 4…

Tags: euler