Click here to Skip to main content
12,400,183 members (49,085 online)
Click here to Skip to main content
Add your own
alternative version

Tagged as

Stats

10.4K views
Posted

Project Euler Problem #3

, 10 Aug 2011 CPOL
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.

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)

Share

About the Author

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

You may also be interested in...

Comments and Discussions

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