Project Euler: Problem 3

The third Euler problem has to do with prime factorization:

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

What is the largest prime factor of the number 600851475143?

Solution

This one I struggled with a bit, cause I wasn’t sure exactly how to do this prime factorization. I knew what it was, and how to do it by hand, but wasn’t quite sure how to do it effective in code. Either way I ended up using something called the Sieve of Eratosthenes. Not the most efficient algorithm for this, if I have understood correctly, but it worked well enough for this use, and it was fairly straight forward to implement with some help from Black Wasp.

I started to make a prime number generator similar to the one I created for Fibonacci numbers in Problem 2.

    public interface IPrimeSequence : IEnumerable<ulong> {}

    public class Eratosthenes : IPrimeSequence
    {
        private readonly List<ulong> knownPrimes;

        public Eratosthenes()
        {
            knownPrimes = new List<ulong> {2, 3};
        }

        #region IPrimeSequence Members
        public IEnumerator<ulong> GetEnumerator()
        {
            // Return the ones we know first
            foreach (var prime in knownPrimes)
                yield return prime;

            // Then find new ones
            var possible = primes.Last();
            while (true)
                if (IsPrime(possible += 2))
                {
                    yield return possible;
                    knownPrimes.Add(possible);
                }
        }

        IEnumerator IEnumerable.GetEnumerator()
        {
            return GetEnumerator();
        }
        #endregion

        private bool IsPrime(ulong value)
        {
            var sqrt = (ulong) Math.Sqrt(value);
            return !knownPrimes
                .TakeWhile(x => x <= sqrt)
                .Any(x => value%x == 0);
        }
    }

It basically starts with the 2 first primes. And for each new requested prime number, it goes through the following odd numbers until it finds one that is not dividable by any of the primes ones we know so far.

Note: I’ve created a separate post about the Sieve of Eratosthenes, which might be updated with some optimizations, et cetera :)

With that prime number generator in place, finding prime factors is pretty straight forward here.

    public static IEnumerable<ulong> GetPrimeFactors(ulong value, IPrimeSequence primeSequence)
    {
        foreach (var prime in primeSequence)
        {
            while (value%prime == 0)
            {
                value /= prime;
                yield return prime;
            }

            if (value == 1)
            {
                yield break;
            }
        }
    }

Now, that is pretty much what is needed to solve this problem. A simple LINQ statement finds the answer.

  var answer = GetPrimeFactors(600851475143, new Eratosthenes()).Max();

Tadaa :D

  • mashrur

    In your code:

    var possible = primes.Last();
    while (true)
    if (IsPrime(possible += 2))
    {
    yield return possible;
    knownPrimes.Add(possible);
    }

    there is no break statement in the while loop so how do you exit the loop? Does the method automatically exit once there is nothing left to yeild?

    • http://www.geekality.net/ Torleif Berger

      I don’t. This method keeps on running infinitely. This works because it stops on each yield return and waits for the call to get the next number (check out the interface of IEnumerator and IEnumerable).

      If you do foreach(var n in new Eratosthenes()) { // something } then it will run forever. However, if you do foreach(var n in new Eratosthenes().Take(500) { // something } then it will just give you the first 500 primes and then stop.

      So this could be used to get pretty many primes. Just remember that although this algorithm is great and fast at first, it will get slower and slower as you get to higher values. So at some point you might want to change to a different algorithm :)