Click here to Skip to main content
Click here to Skip to main content

Project Euler Problem #3

, 10 Aug 2011
Rate this:
Please Sign up or sign in to vote.
CodeProjectTime 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 to acc

Time for Project Euler Problem 3.

The prime factors of 13195 are 5, 7, 13 and 29.
<br />
<br />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 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();

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

About the Author

Jared Wallace
Business Analyst
United States United States
Visit my blog, Aimless Technical Babble

Comments and Discussions

 
-- There are no messages in this forum --
| Advertise | Privacy | Mobile
Web01 | 2.8.140721.1 | Last Updated 10 Aug 2011
Article Copyright 2011 by Jared Wallace
Everything else Copyright © CodeProject, 1999-2014
Terms of Service
Layout: fixed | fluid