Euler #3

The third Euler problem was harder than I expected it to be. It's fairly straightforward, but the parameters are designed to keep you from solving it in what seemed to me to be the most straightforward way.

Take a look:

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

What is the largest prime factor of the number 600851475143?

My first impulse was to apply the Sieve of Eratosthenes to all integers 1-600851475143. 600851475143, however, is too large for most .NET data types, and a list or array of 600851475143 long integers threw an “out of memory” exception: someone calculated that such an array would be 560GB, far beyond .NET's 2GB limit on lists and arrays. In any case, I'm sure my solution is not memory efficient in any sense. I capped my search at the square root of 600851475143, which would capture either all or all but one of the number's prime factors. I just added a branch at the end to either print the result or find the last factor and print that.

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace Problem3
{
    class Program
    {
        static void Main(string[] args)
        {
            int ceiling = (int)Math.Sqrt(600851475143);
            List<int> eratosthenes = new List<int>();
            List<int> factorials = new List<int>();
            long runningValue = 1;

            for (int i = 2; i &lt; ceiling; i++)
            {
                eratosthenes.Add(i);
            }

            for (int i = 0; i &lt; eratosthenes.Count(); i++)
            {
                eratosthenes.RemoveAll(x => (x != eratosthenes[i]) && (x % eratosthenes[i] == 0));
                if (600851475143 % eratosthenes[i] == 0) { factorials.Add(eratosthenes[i]); }
            }

            for (int i = 0; i < factorials.Count(); i++)
            {
                runningValue *= factorials[i];
            }

            if (runningValue == 600851475143)
            { Console.WriteLine("The largest prime factorial of 600851475143 is {0}", factorials.Max()); }
            else { Console.WriteLine("The largest prime factorial of 600851475143 is {0}", (600851475143 / runningValue)); }
        }
    }
}