Project Euler Problem #3

Time for Project Euler Problem 3.

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

What is the largest prime factor of the number 600851475143 ?

Ah. Prime numbers. This should be fun.

Well, first I think we need a fast and efficient way to generate prime numbers. There are many different ways to accomplish this, but I think making an iterator class to generate them will be best. It will be very similar to the generator we had for Problem Two to generate the Fibonacci sequence.

Here is our generator class:

public class Primes : IEnumerable<long>
{
    private List<long> _primes;

    public Primes()
    {
        _primes = new List<long>();
        _primes.Add(2);
    }

    public IEnumerator<long> GetEnumerator()
    {
        Func<long, bool> IsPrime = n => _primes.TakeWhile
        (i => i <= (long)Math.Sqrt(n)).Count(i => (n % i).Equals(0)).Equals(0);

        yield return 2;
        long next = 3;

        while (true)
        {
            if (IsPrime(next))
            {
                _primes.Add(next);
                yield return next;
            }
            next += 2;
        }
    }

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

Now that we have our generator, all we have to do is generate primes up to the square root of 600851475143 and then take the largest factor. Easy enough.

long number = 600851475143;
return new Primes().TakeWhile
(i => i < (long)Math.Sqrt(number)).Where(i => (number % i).Equals(0)).Last();

CodeProject