Click here to Skip to main content
13,738,050 members
Click here to Skip to main content
Add your own
alternative version

Tagged as


Posted 10 Aug 2011
Licenced CPOL

Project Euler Problem #3

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

    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))
                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();


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

You may also be interested in...


Comments and Discussions

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