Project Euler - Problem 3: Largest Prime Factor

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

What is the largest prime factor of the number 600851475143?

---

Explanation:

Remember those factor trees you had to make as a kid? Yup, we are going to be doing something similar. We will start at 3 (because the number we are trying to factor is not divisible by 2..) and will start trying to divide until we cannot divide any longer. If you wanted to be safe, you could add a special if statement clause to check for the prime 2 in case you ever wanted to change the large number being factored.

Solution:

public static readonly ulong Number = 600851475143;
    
    public static void Main(string[] args)
    {     
        ulong number = Number;
        ulong largestFactor = 2;
        
        while(number > 1 && number % largestFactor == 0)
        {
            number /= largestFactor;
        }
        
        largestFactor = 3;
        
        while(number > 1)
        {
            while(number % largestFactor == 0)
            {
                number /= largestFactor;
            }
            if(number != 1)
            {
                largestFactor += 2;   
            }
        }
        
        Console.WriteLine(largestFactor);
    }

This simple solution can be found here.

An Improved Solution

We can improve the function slightly by understanding that the largest factor must be less than or equal to the square root of the number. Say the number is 50. We know the largest factor must be less than 8 because 8 * 8 = 64. In effect, we can eliminate quite a bit of the sample space!

public static readonly ulong Number = 600851475143;
    
    public static void Main(string[] args)
    {       
        ulong number = Number;
        ulong largestFactor = 2;
        
        ulong largestRoot = (ulong)Math.Sqrt(number);
        
        while(number > 1 && number % largestFactor == 0)
        {
            number /= largestFactor;
        }
        
        largestFactor = 3;
        
        while(number > 1 && largestFactor < largestRoot)
        {
            while(number % largestFactor == 0)
            {
                number /= largestFactor;
            }
            if(number != 1)
            {
                largestFactor += 2;   
            }
        }
        
        Console.WriteLine(largestFactor);
    }

This solution can be found here.

Conclusion:

We can see that the optimized version saves us a little bit of computational power, but just barely is noticeable. We may be able to get away with reducing from ulong to double, but since this problem was not going to be working with negative numbers it seemed easier to guarantee the extra space. I am not overly fond of the two separate while loops doing essentially the same logic, instead it may be better to try to combine them and have a check for the largestFactor = 2 inside the single while loop.

Of course we could always try to break this out into an object oriented approach, but that seems overkill at the moment.