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
public class Primes : IEnumerable<long>
private List<long> _primes;
_primes = new List<long>();
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;
yield return next;
next += 2;
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();