Project Euler Problem 3

For Problem 3, the goal is to find the largest prime factor of the number 600851475143. For this, I created a prime number generator in my NumberGenerator class, called Primes(), which takes a single parameter indicating the largest prime number we want returned. It uses the "yield return" operator to return the primes.

public static IEnumerable Primes(long max)
{
var nonPrimes = new bool[max + 1];

for (long i = 2; i <= max; i++)
{
if (nonPrimes[i] == false)
{
for (var j = i * i; j <= max; j += i)
{
nonPrimes[j] = true;
}
yield return i;
}
}
}

I then call that generator using the square root of the target number as the maximum prime number to return. I use a Linq where clause to only return prime numbers that are factors of the target number, then use the Last() method to just return the last of these. This gives me my answer.

public void Run()
{
const long target = 600851475143L;
int sqrt = (int)Math.Sqrt(target);

long answer = NumberGenerator.Primes(sqrt).Where(x => target % x == 0).Last();

Console.WriteLine("answer = {0}", answer);
}

I was pretty happy with how short the code for this turned out, once the prime number generator was written. I've since used the prime number generator quite a bit in other Euler problems, so making it separate was a good decision.